Problem: 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.

Solution (in JAVA):

Solution:
//package GeneralProblems;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class ShortProgram {
	static class pair{
		int q,val;
		public pair(int q, int val) {
			this.val = val;
			this.q = q;
		}
		public String toString() {
			return q+" "+val;
		}
	}
public static void main(String[] args) throws IOException{
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	int n = Integer.parseInt(in.readLine());
	pair op [] = new pair[n];
	ArrayList<pair> opShort = new ArrayList<pair>();
	for (int i = 0; i < op.length; i++) {
		StringTokenizer st= new StringTokenizer(in.readLine());
		String operand = st.nextToken();
		int q = 0;
		if(operand.equals("&"))
			q = 1;
		else if(operand.equals("^"))
			q = 2;
		op[i]=new pair(q,Integer.parseInt(st.nextToken()));
		// 0==| 
	 }
	
	int [] output = new int[12];
	int [] operations = new int[12];
	Arrays.fill(operations, -1);
	Arrays.fill(output, -1);
	for (int i = 0; i < op.length; i++) {
		pair cur = op[i];
		if(op[i].q==0) {
			String val = Integer.toBinaryString(cur.val);
			int len = 12-val.length();
			int count = 0;
			for (int j = len; j <12 ; j++) {
				if(val.charAt(count++)=='1') {
					operations[j]=0;
					output[j]=1;
				}
			}
		}else if(op[i].q==1) {
			int count = 0;
			String val = Integer.toBinaryString(cur.val);
			int len = 12-val.length();
			for (int j = 0; j <len; j++) {
				output[j]=0;
				operations[j]=1;
			}
			for (int j = len; j <12 ; j++) {
				if(val.charAt(count++)=='0') {
					output[j]=0;
					operations[j]=1;
				}
			}
		}else {
			String val = Integer.toBinaryString(cur.val);
			int len = 12-val.length();
			int count = 0;
			for (int j = len; j <12 ; j++) {
				if(val.charAt(count++)=='1') {
					if(output[j]==-1) 
						if(operations[j]==2)
							operations[j]=0;
						else
							operations[j]=2;
					else if(output[j]==1) {
						output[j]=0;
						operations[j]=1;
					}else if(output[j]==0) {
						output[j]=1;
						operations[j]=0;
					}
				}
			}
			
		}
//		System.out.println(Arrays.toString(operations));
	}
//	System.out.println(Arrays.toString(output));
//	System.out.println(Arrays.toString(operations));
	int xor = 0;
	for (int i = 0; i < operations.length; i++) {
		if(operations[i]==2)
			xor|=1<<(11-i);
	}
//	System.out.println(xor);
	int add = (1<<10)-1;
//	System.out.println(Integer.toBinaryString(125)+" "+add);
//	System.out.println(Integer.toBinaryString(377)+" "+add);
//	System.out.println(Integer.toBinaryString(1019)+" "+add);
	for (int i = 0; i < output.length; i++) {
		if(output[i]==0)
			add &=~(1<<(11-i));
	}
	int or = 0;
	for (int i = 0; i < output.length; i++) {
		if(output[i]==1)
			or|=(1<<(11-i));
	}
	System.out.println(3);
	System.out.println("| "+or);
	System.out.println("& "+add);
	System.out.println("^ "+xor);
//	
//	
//	
//	
//	
//	
//	
//	
//	
//	
//	
//	
//	int prevQ = op[0].q;
//	int valSofar = op[0].val;
//	for (int i = 1; i < op.length; i++) {
//		if(op[i].q == prevQ)
//		{
//			switch(prevQ) {
//			case 0: valSofar |=op[i].val;break;
//			case 1: valSofar &=op[i].val;break;
//			case 2: valSofar ^=op[i].val;break;
//			}
//		}else {
//			if((prevQ==0&& valSofar == 0)||(prevQ==2&&valSofar==0))
//			{
//				
//			}else {
//			opShort.add(new pair(prevQ,valSofar));
//			prevQ = op[i].q;
//			valSofar = op[i].val;
//			}
//		}
//	}
//	if(!((prevQ==0&& valSofar == 0)||(prevQ==2&&valSofar==0)))
//	opShort.add(new pair(prevQ,valSofar));
//	//i have three scenarios
//	int [] x = new int[12];
//	boolean useful[] = new boolean[opShort.size()];
//	Arrays.fill(useful, true );
//	Arrays.fill(x, -1);
//	int count = 0;
//	int [] newArray;
////	System.out.println(opShort.size());
//	newArray = new int[x.length];
//	int q = 0, val=0;
//	if(opShort.size()!=0) {
//	 q = opShort.get(0).q;
//	 val = opShort.get(0).val;
//	if(q==1) {
//		Arrays.fill(newArray, 0);
//		String cur = Integer.toBinaryString(val);
//		for (int j = cur.length()-1; j >=0; j--) {
//			if(cur.charAt(j)=='1') {
//				newArray[newArray.length-1-(cur.length()-1-j)]=x[cur.length()-1-j];
//			}
//		}
//		boolean same = equal(newArray,x);
//	}else if(q==0) {
//		String cur = Integer.toBinaryString(val);
//		for (int j = cur.length()-1; j >=0; j--) {
//			if(cur.charAt(j)=='1') {
//				newArray[newArray.length-1-(cur.length()-1-j)]=1;
//			}
//		}
//		boolean same = equal(newArray,x);
//	}else {
//		String cur = Integer.toBinaryString(val);
//		for (int j = cur.length()-1; j >=0; j--) {
//			if(cur.charAt(j)=='1') {
//				if(newArray[newArray.length-1-(cur.length()-1-j)]!=-1)
//					newArray[newArray.length-1-(cur.length()-1-j)]^=1;
//			}
//		}
//	}
//	x = newArray;
//
//	
//	
//	
//	}
//	for (int i = 1; i < opShort.size(); i++) {
////		System.out.println(Arrays.toString(x));
//		newArray = new int[12];
//		for (int j = 0; j < newArray.length; j++) {
//			newArray[j]=x[j];
//		}
//		 q = opShort.get(i).q;
//		 val = opShort.get(i).val;
//		if(q==1) {
//			Arrays.fill(newArray, 0);
//			String cur = Integer.toBinaryString(val);
//			for (int j = cur.length()-1; j >=0; j--) {
//				if(cur.charAt(j)=='1') {
//					newArray[newArray.length-1-(cur.length()-1-j)]=x[cur.length()-1-j];
//				}
//			}
//			boolean same = equal(newArray,x);
//			if(same)
//				useful[i]=false;
//		}else if(q==0) {
////			System.out.println("hello");
//			String cur = Integer.toBinaryString(val);
////			System.out.println(cur+" "+val);
//			for (int j = cur.length()-1; j >=0; j--) {
//				if(cur.charAt(j)=='1') {
//					newArray[newArray.length-1-(cur.length()-1-j)]=1;
//				}
//			}
//			boolean same = equal(newArray,x);
//			if(same)
//				useful[i]=false;
//		}else {
//			String cur = Integer.toBinaryString(val);
//			for (int j = cur.length()-1; j >=0; j--) {
//				if(cur.charAt(j)=='1') {
//					if(newArray[newArray.length-1-(cur.length()-1-j)]!=-1)
//						newArray[newArray.length-1-(cur.length()-1-j)]^=1;
//				}
//			}
//			boolean same = equal(newArray,x);
////			System.out.println(same);
//			if(same)
//				useful[i]=false;
//		}
//		if(useful[i]==false)
//		count++;
////		System.out.println(Arrays.toString(newArray));
//		x = newArray;
//	}
////	System.out.println(opShort.toString());
//	PrintWriter out =new PrintWriter(System.out);
////	System.out.println(count);
//	out.println(opShort.size()-count);
//	for (int j = 0; j < opShort.size(); j++) {
//		if(useful[j])
//			out.println(conv(opShort.get(j).q)+" "+opShort.get(j).val );
//	}
//	out.flush();out.close();
}
static String conv(int x) {
	if(x==1)
		return "&";
	else if(x==0)
		return "|";
	else return "^";
				}
static boolean equal(int [] one, int []two) {
	for (int i = 0; i < two.length; i++) {
		if(one[i]!=two[i])
			return false;
	}
	return true;
}

}