Petya learned a new programming language CALPAS. A program in this language always takes one non-negative integer and returns one non-negative integer as well.

In the language, there are only three commands: apply a bitwise operation AND, OR or XOR with a given constant to the current integer. A program can contain an arbitrary sequence of these operations with arbitrary constants from 0 to 1023. When the program is run, all operations are applied (in the given order) to the argument and in the end the result integer is returned.

Petya wrote a program in this language, but it turned out to be too long. Write a program in CALPAS that does the same thing as the Petya's program, and consists of no more than 5 lines. Your program should return the same integer as Petya's program for all arguments from 0 to 1023.

Input

The first line contains an integer n (1 ≤ n ≤ 5·105) — the number of lines.

Next n lines contain commands. A command consists of a character that represents the operation ("&", "|" or "^" for AND, OR or XOR respectively), and the constant xi 0 ≤ xi ≤ 1023.

Output

Output an integer k (0 ≤ k ≤ 5) — the length of your program.

Next k lines must contain commands in the same format as in the input.

Examples

Input

3
| 3
^ 2
| 1


Output

2
| 3
^ 2


Input

3
&amp; 1
&amp; 3
&amp; 5


Output

1
&amp; 1


Input

3
^ 1
^ 2
^ 3


Output

0

Note

You can read about bitwise operations in <https://en.wikipedia.org/wiki/Bitwise_operation>.

Second sample:

Let x be an input of the Petya's program. It's output is ((x&1)&3)&5 = x&(1&3&5) = x&1. So these two programs always give the same outputs.
import java.io.*;
import java.util.*;

public class A {

	public static void main(String[] args) throws IOException {

		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

		int n = sc.nextInt();
		String[] ops = new String[n];
		int[] cnst = new int[n];
		for(int i = 0; i < n; ++i)
		{
			String[] t = sc.nextLine().split(" ");
			ops[i] = t[0];
			cnst[i] = Integer.parseInt(t[1]);
		}

		int orCnst = 0, andCnst = 1023, xorCnst = 0;
		for(int bit = 0; bit < 10; ++bit)
		{
			int r0 = 0, r1 = 1;
			for(int i = 0; i < n; ++i)
			{
				int x = cnst[i] >> bit & 1;
				if(ops[i].equals("|")) { r0 |= x; r1 |= x; }
				else if(ops[i].equals("&")) { r0 &= x; r1 &= x; }
				else { r0 ^= x; r1 ^= x; }
			}
			r1 = r1 << 1 | r0;
			if(r1 == 0b00) { andCnst &= ~(1 << bit); }
			else if(r1 == 0b01) { xorCnst |= 1 << bit; }
			else if(r1 == 0b11) { orCnst |= 1 << bit; }
		}

		out.println(3);
		out.println("| " + orCnst);
		out.println("& " + andCnst);
		out.println("^ " + xorCnst);
		out.close();
	}


	static class Scanner
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

		public Scanner(FileReader s) throws FileNotFoundException {	br = new BufferedReader(s);}

		public String next() throws IOException
		{
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {return Integer.parseInt(next());}

		public long nextLong() throws IOException {return Long.parseLong(next());}

		public String nextLine() throws IOException {return br.readLine();}

		public double nextDouble() throws IOException { return Double.parseDouble(next()); }

		public boolean ready() throws IOException {return br.ready();}
	}
}