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:
import java.io.*;
import java.util.*;
import java.lang.*;

public class Main {

    static StreamTokenizer st;
    static PrintWriter out;

    static int[] bits;

    public static void main(String[] args) throws IOException {
        st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(System.out);
        bits = new int[10];
        Arrays.fill(bits, -1);
        st.ordinaryChar('|');
        st.ordinaryChar('&');
        st.ordinaryChar('^');
        int n = ri();
        while (n-- > 0) {
            char c = (char) st.nextToken();
            int x = ri();
            char[] xa = toArr(x);
            switch (c) {
                case '^': doXor(xa); break;
                case '&': doAnd(xa); break;
                case '|': doOr(xa);
            }
        }
        ArrayList<String> output = new ArrayList();
        int xor = 0;
        for (int i = 0; i < 10; ++i)
            if (bits[i] == -2)
                xor |= (1 << (10 - i - 1));
        if (xor != 0)
            output.add("^ " + xor);

        int and = 1023;
        for (int i = 0; i < 10; ++i)
            if (bits[i] == 0)
                and ^= (1 << (10 - i - 1));
        if (and != 1023)
            output.add("& " + and);

        int or = 0;
        for (int i = 0; i < 10; ++i)
            if (bits[i] == 1)
                or |= (1 << (10 - i - 1));
        if (or != 0)
            output.add("| " + or);

        out.println(output.size());
        for (String s : output)
            out.println(s);
        out.close();
    }

    static void doAnd(char[] l) {
        for (int i = 0; i < 10; ++i)
            if (l[i] == '0')
                bits[i] = 0;
    }

    static void doOr(char[] l) {
        for (int i = 0; i < 10; ++i)
            if (l[i] == '1')
                bits[i] = 1;
    }

    static void doXor(char[] l) {
        for (int i = 0; i < 10; ++i)
            if (l[i] == '1')
                if (bits[i] == -1) bits[i] = -2;
                else if (bits[i] == -2) bits[i] = -1;
                else bits[i] = (bits[i] + 1) % 2;
    }


    static char[] toArr(int i) {
        return String.format("%10s", Integer.toBinaryString(i)).replace(" ", "0").toCharArray();
    }

    static String rs() throws IOException {
        st.nextToken();
        return st.sval;
    }

    static long rl() throws IOException {
        st.nextToken();
        return (long) st.nval;
    }

    static int ri() throws IOException {
        st.nextToken();
        return (int) st.nval;
    }
}