Natasha travels around Mars in the Mars rover. But suddenly it broke down, namely — the logical scheme inside it. The scheme is an undirected tree (connected acyclic graph) with a root in the vertex 1, in which every leaf (excluding root) is an input, and all other vertices are logical elements, including the root, which is output. One bit is fed to each input. One bit is returned at the output.

There are four types of logical elements: [AND](https://en.wikipedia.org/wiki/Logical_conjunction) (2 inputs), [OR](https://en.wikipedia.org/wiki/Logical_disjunction) (2 inputs), [XOR](https://en.wikipedia.org/wiki/Exclusive_or) (2 inputs), [NOT](https://en.wikipedia.org/wiki/Negation) (1 input). Logical elements take values from their direct descendants (inputs) and return the result of the function they perform. Natasha knows the logical scheme of the Mars rover, as well as the fact that only one input is broken. In order to fix the Mars rover, she needs to change the value on this input.

For each input, determine what the output will be if Natasha changes this input.

Input

The first line contains a single integer n (2 ≤ n ≤ 10^6) — the number of vertices in the graph (both inputs and elements).

The i-th of the next n lines contains a description of i-th vertex: the first word "AND", "OR", "XOR", "NOT" or "IN" (means the input of the scheme) is the vertex type. If this vertex is "IN", then the value of this input follows (0 or 1), otherwise follow the indices of input vertices of this element: "AND", "OR", "XOR" have 2 inputs, whereas "NOT" has 1 input. The vertices are numbered from one.

It is guaranteed that input data contains a correct logical scheme with an output produced by the vertex 1.

Output

Print a string of characters '0' and '1' (without quotes) — answers to the problem for each input in the ascending order of their vertex indices.

Example

Input

10
AND 9 4
IN 1
IN 1
XOR 6 5
AND 3 7
IN 0
NOT 10
IN 1
IN 1
AND 2 8


Output

10110

Note

The original scheme from the example (before the input is changed):

<image>

Green indicates bits '1', yellow indicates bits '0'.

If Natasha changes the input bit 2 to 0, then the output will be 1.

If Natasha changes the input bit 3 to 0, then the output will be 0.

If Natasha changes the input bit 6 to 1, then the output will be 1.

If Natasha changes the input bit 8 to 0, then the output will be 1.

If Natasha changes the input bit 9 to 0, then the output will be 0.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Iterator;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.function.Consumer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        MyScan in = new MyScan(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        public void solve(int testNumber, MyScan in, PrintWriter out) {
            int n = in.nextInt();


            int[][] edges = new int[2][n - 1];

            boolean[] starts = new boolean[n];
            int[] type = new int[n];

            int[][] nn = new int[n][];

            int l1, l2;
            int ec = 0;
            for (int f = 0; f < n; f++) {
                String l = in.next().toUpperCase();
                switch (l) {
                    case "OR":
                        type[f] = 0;
                        l1 = in.nextInt() - 1;
                        l2 = in.nextInt() - 1;
                        edges[0][ec] = f;
                        edges[1][ec++] = l1;
                        edges[0][ec] = f;
                        edges[1][ec++] = l2;

                        nn[f] = new int[]{l1, l2};
                        break;
                    case "IN":
                        type[f] = 1;
                        starts[f] = in.nextInt() == 1;
                        break;
                    case "XOR":
                        type[f] = 2;
                        l1 = in.nextInt() - 1;
                        l2 = in.nextInt() - 1;
                        edges[0][ec] = f;
                        edges[1][ec++] = l1;
                        edges[0][ec] = f;
                        edges[1][ec++] = l2;
                        nn[f] = new int[]{l1, l2};
                        break;
                    case "AND":
                        type[f] = 3;
                        l1 = in.nextInt() - 1;
                        l2 = in.nextInt() - 1;
                        edges[0][ec] = f;
                        edges[1][ec++] = l1;
                        edges[0][ec] = f;
                        edges[1][ec++] = l2;
                        nn[f] = new int[]{l1, l2};
                        break;
                    case "NOT":
                        type[f] = 4;
                        l1 = in.nextInt() - 1;
                        edges[0][ec] = f;
                        edges[1][ec++] = l1;
                        nn[f] = new int[]{l1};
                        break;
                }
            }

            Tree tree = TreeReader.byEdges(edges);

            TaskD.Result[] results = new TaskD.Result[n];
            tree.setOnRemove(l -> {

                if (type[l[0]] == 1) {
                    results[l[0]] = new TaskD.Result(starts[l[0]], l[0]);
                } else {
                    switch (type[l[0]]) {
                        case 0:
                            results[l[0]] = TaskD.Result.or(results[nn[l[0]][0]], results[nn[l[0]][1]]);
                            break;
                        case 2:
                            results[l[0]] = TaskD.Result.xor(results[nn[l[0]][0]], results[nn[l[0]][1]]);
                            break;
                        case 3:
                            results[l[0]] = TaskD.Result.and(results[nn[l[0]][0]], results[nn[l[0]][1]]);
                            break;
                        case 4:
                            results[l[0]] = TaskD.Result.not(results[nn[l[0]][0]]);
                            break;

                    }
                }
            });

            tree.dfs(0);

            TaskD.Result outs = results[0];


            int[] ans = new int[n];
            Arrays.fill(ans, -1);
            for (int s : outs.zero) {
                ans[s] = 0;
            }
            for (int s : outs.one) {
                ans[s] = 1;
            }
            for (int t : ans) {
                if (t != -1) {
                    out.print(t);
                }
            }

        }

        private static final class Result {
            boolean simple;
            AList zero;
            AList one;

            public Result(boolean start, int i) {
                simple = start;
                zero = new AList();
                one = new AList();
                if (start) {
                    zero.add(i);
                } else {
                    one.add(i);
                }
            }

            public Result() {
                zero = new AList();
                one = new AList();
            }

            public static TaskD.Result or(TaskD.Result result2, TaskD.Result result1) {
                TaskD.Result nr = new TaskD.Result();
                nr.simple = result2.simple || result1.simple;

                nr.one(result2.one);
                nr.one(result1.one);
                if (result2.simple) {
                    nr.one(result1.zero);
                } else {
                    nr.zero(result1.zero);
                }
                if (result1.simple) {
                    nr.one(result2.zero);
                } else {
                    nr.zero(result2.zero);
                }
                return nr;
            }

            private void one(AList oth) {
                if (one == null) {
                    one = oth;
                } else {
                    one = one.merge(oth);
                }
            }

            private void zero(AList oth) {
                if (zero == null) {
                    zero = oth;
                } else {
                    zero = zero.merge(oth);
                }
            }

            public static TaskD.Result xor(TaskD.Result result2, TaskD.Result result1) {
                TaskD.Result nr = new TaskD.Result();
                nr.simple = result2.simple ^ result1.simple;


                if (result2.simple) {
                    nr.one(result1.zero);
                    nr.zero(result1.one);
                } else {
                    nr.zero(result1.zero);
                    nr.one(result1.one);
                }
                if (result1.simple) {
                    nr.one(result2.zero);
                    nr.zero(result2.one);
                } else {
                    nr.zero(result2.zero);
                    nr.one(result2.one);
                }

                return nr;
            }

            public static TaskD.Result and(TaskD.Result result2, TaskD.Result result1) {
                TaskD.Result nr = new TaskD.Result();
                nr.simple = result2.simple && result1.simple;


                nr.zero(result2.zero);
                nr.zero(result1.zero);
                if (result2.simple) {
                    nr.one(result1.one);
                } else {
                    nr.zero(result1.one);
                }
                if (result1.simple) {
                    nr.one(result2.one);
                } else {
                    nr.zero(result2.one);
                }
                return nr;
            }

            public static TaskD.Result not(TaskD.Result result) {
                TaskD.Result nr = new TaskD.Result();
                nr.simple = !result.simple;
                nr.one = result.zero;
                nr.zero = result.one;
                return nr;
            }

        }

    }

    static class MyScan {
        private final InputStream in;
        private byte[] inbuf = new byte[1024];
        public int lenbuf = 0;
        public int ptrbuf = 0;

        public MyScan(InputStream in) {
            this.in = in;
        }

        private int readByte() {
            if (lenbuf == -1) throw new InputMismatchException();
            if (ptrbuf >= lenbuf) {
                ptrbuf = 0;
                try {
                    lenbuf = in.read(inbuf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (lenbuf <= 0) return -1;
            }
            return inbuf[ptrbuf++];
        }

        public boolean isSpaceChar(int c) {
            return !(c >= 33 && c <= 126);
        }

        public int skip() {
            int b;
            while ((b = readByte()) != -1 && isSpaceChar(b)) ;
            return b;
        }

        public String next() {
            int b = skip();
            StringBuilder sb = new StringBuilder();
            while (!(isSpaceChar(b))) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }

        public int nextInt() {
            int num = 0, b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }

            while (true) {
                if (b >= '0' && b <= '9') {
                    num = num * 10 + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

    }

    static class TreeReader {
        public static Tree byEdges(int[][] pn) {
            return new Tree(pn(pn, pn[0].length + 1));
        }

        public static int[][] pn(int[][] x, int n) {
            int[] ct = new int[n];
            int[][] res = new int[n][];
            for (int v : x[0]) {
                ct[v]++;
            }
            for (int v : x[1]) {
                ct[v]++;
            }
            for (int l = 0; l < n; l++) {
                res[l] = new int[ct[l]];
            }
            for (int i = 0; i < x[0].length; i++) {
                res[x[0][i]][--ct[x[0][i]]] = x[1][i];
                res[x[1][i]][--ct[x[1][i]]] = x[0][i];
            }
            return res;
        }

    }

    static class Tree {
        public int[][] data;
        Consumer<int[]> onAdd;
        Consumer<int[]> onRemove;

        public Tree(int[][] data) {
            this.data = data;
        }

        public Tree(AList[] data) {
            this(AList.convert(data));
        }

        public void setOnRemove(Consumer<int[]> onRemove) {
            this.onRemove = onRemove;
        }

        private int[] dfs(int start, Consumer<int[]> onAdd, Consumer<int[]> onRemove) {
            Tree.P[] n = new Tree.P[data.length * 2];
            int toVisit = 0;
            n[toVisit++] = new Tree.P(start, true, -1);
            boolean[] vis = new boolean[data.length];
            vis[start] = true;
            int[] level = new int[data.length];
            while (toVisit > 0) {
                Tree.P ppr = n[--toVisit];
                if (!ppr.b) {
                    if (onRemove != null)
                        onRemove.accept(new int[]{ppr.ind, level[ppr.ind], ppr.parent});
                    continue;
                }
                ppr.b = false;
                int i = ppr.ind;
                n[toVisit++] = ppr;
                if (onAdd != null)
                    onAdd.accept(new int[]{ppr.ind, level[ppr.ind], ppr.parent});
                for (int kk : data[i]) {
                    if (!vis[kk]) {
                        vis[kk] = true;
                        level[kk] = level[i] + 1;
                        n[toVisit++] = new Tree.P(kk, true, i);
                    }
                }
            }
            return level;
        }

        public int[] dfs(int start) {
            return dfs(start, onAdd, onRemove);
        }

        public static class P {
            private boolean b;
            private final int ind;
            private final int parent;

            public P(int i, boolean b, int par) {
                this.ind = i;
                this.b = b;
                this.parent = par;
            }

        }

    }

    static class AList implements Iterable<Integer> {
        int[] data;
        int size = 0;

        public AList(int n) {
            this(4, false);
        }

        public AList(int n, boolean explicit) {
            if (explicit) {
                this.data = new int[n];
            } else {
                this.data = new int[Math.max(Integer.highestOneBit(n - 1) << 1, 4)];
            }
        }

        public AList() {
            this(4);
        }

        public AList(int[] data) {
            this(data.length);
            System.arraycopy(data, 0, this.data, 0, data.length);
            size = data.length;
        }

        AList(int[] data, int s) {
            this.data = data;
            this.size = s;
        }

        public static int[][] convert(AList[] data) {
            int[][] res = new int[data.length][];
            for (int s = 0; s < data.length; s++) {
                res[s] = data[s].toArray();
            }
            return res;
        }

        public void add(int k) {
            if (size == data.length) {
                data = Arrays.copyOf(data, data.length << 1);
            }
            data[size++] = k;
        }


        public Iterator<Integer> iterator() {


            int[] m = new int[1];
            return new Iterator<Integer>() {

                public boolean hasNext() {
                    return m[0] < AList.this.size;
                }


                public Integer next() {
                    return AList.this.data[m[0]++];
                }
            };
        }


        public String toString() {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < size; i++) {
                sb.append(data[i]).append(' ');
            }
            return sb.toString();
        }

        public void addAll(AList other) {
            int nl = data.length;
            while (nl < size + other.size) {
                nl <<= 1;
            }
            if (nl != data.length) {
                data = Arrays.copyOf(data, nl);
            }
            System.arraycopy(other.data, 0, data, size, other.size);
            size += other.size;
        }

        public AList merge(AList other) {
            if (other.size > this.size) {
                return other.merge(this);
            }
            addAll(other);
            return this;
        }

        public int[] toArray() {
            return Arrays.copyOf(data, size);
        }

    }
}

