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.OutputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.io.FilterInputStream; import java.io.BufferedInputStream; import java.io.InputStream; /** * Built using CHelper plug-in * Actual solution is at the top * * @author khokharnikunj8 */ public class Main { public static void main(String[] args) { InputStream inputStream = System.in; OutputStream outputStream = System.out; ScanReader in = new ScanReader(inputStream); PrintWriter out = new PrintWriter(outputStream); TaskC solver = new TaskC(); solver.solve(1, in, out); out.close(); } static class TaskC { public void solve(int testNumber, ScanReader in, PrintWriter out) { int num = in.scanInt(); int aa = 1023, bb = 0, c; char a; for (int i = 0; i < num; i++) { a = in.scanChar(); c = in.scanInt(); if (a == '|') { aa |= c; bb |= c; } else if (a == '^') { aa ^= c; bb ^= c; } else { aa &= c; bb &= c; } } if (aa == 1023 && bb == 0) { out.println(0); return; } int ans1 = 0, ans2 = 0, ff1, ff2, ff; for (int i = 9; i >= 0; i--) { ff = 1 << i; ff1 = (aa & ff); ff2 = (bb & ff); if (ff1 == ff&& ff2 == ff) ans1 += ff; else if (ff1 == 0 && ff2 == ff) ans2 += ff; else if (ff1 == 0 && ff2 == 0) { ans1 += (ff); ans2 += ff; } } out.println(2); out.println("| " + ans1); out.println("^ " + ans2); } } static class ScanReader { private byte[] buf = new byte[4 * 1024]; private int index; private BufferedInputStream in; private int total; public ScanReader(InputStream inputStream) { in = new BufferedInputStream(inputStream); } private int scan() { if (index >= total) { index = 0; try { total = in.read(buf); } catch (Exception e) { e.printStackTrace(); } if (total <= 0) return -1; } return buf[index++]; } public char scanChar() { int c = scan(); while (isWhiteSpace(c)) c = scan(); return (char) c; } public int scanInt() { int integer = 0; int n = scan(); while (isWhiteSpace(n)) n = scan(); int neg = 1; if (n == '-') { neg = -1; n = scan(); } while (!isWhiteSpace(n)) { if (n >= '0' && n <= '9') { integer *= 10; integer += n - '0'; n = scan(); } } return neg * integer; } private boolean isWhiteSpace(int n) { if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true; else return false; } } }