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 \le n \le 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.
[samples]
## Note
The original scheme from the example (before the input is changed):
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$.
娜塔莎驾驶火星车在火星上旅行。但突然它坏了——内部的逻辑电路出现了故障。该电路是一个无向树（连通无环图），根节点为顶点 $1$，其中每个叶子节点（除根外）均为输入，其余所有顶点均为逻辑元件，包括根节点（作为输出）。每个输入端输入一个比特，输出端返回一个比特。
逻辑元件有四种类型：AND（2 个输入）、OR（2 个输入）、XOR（2 个输入）、NOT（1 个输入）。逻辑元件从其直接子节点（输入）获取值，并返回其所执行函数的结果。娜塔莎知道火星车的逻辑电路，并且知道只有一个输入损坏。为了修复火星车，她需要改变该输入的值。
对于每个输入，请确定当娜塔莎改变该输入时，输出会变成什么。
第一行包含一个整数 $n$（$2 lt.eq n lt.eq 10^6$）——图中顶点的数量（包括输入和元件）。
接下来的 $n$ 行中，第 $i$ 行描述第 $i$ 个顶点：第一个单词为 "AND"、"OR"、"XOR"、"NOT" 或 "IN"（表示该顶点为输入）。若该顶点为 "IN"，则其后跟随该输入的值（0 或 1）；否则，跟随该元件的输入顶点的编号："AND"、"OR"、"XOR" 有 2 个输入，"NOT" 有 1 个输入。顶点编号从 1 开始。
保证输入数据构成一个合法的逻辑电路，且输出由顶点 $1$ 产生。
请输出一个由字符 _'0'_ 和 _'1'_ 组成的字符串（不含引号）——按顶点编号升序排列，每个输入改变后对应的输出结果。
## Input
第一行包含一个整数 $n$（$2 lt.eq n lt.eq 10^6$）——图中顶点的数量（包括输入和元件）。第 $i$ 行描述第 $i$ 个顶点：第一个单词为 "AND"、"OR"、"XOR"、"NOT" 或 "IN"（表示该顶点为输入）。若该顶点为 "IN"，则其后跟随该输入的值（0 或 1）；否则，跟随该元件的输入顶点的编号："AND"、"OR"、"XOR" 有 2 个输入，"NOT" 有 1 个输入。顶点编号从 1 开始。保证输入数据构成一个合法的逻辑电路，且输出由顶点 $1$ 产生。
## Output
请输出一个由字符 _'0'_ 和 _'1'_ 组成的字符串（不含引号）——按顶点编号升序排列，每个输入改变后对应的输出结果。
[samples]
## Note
示例中的原始电路（在输入改变前）：绿色表示比特 _'1'_，黄色表示比特 _'0'_。如果娜塔莎将输入位 $2$ 改为 $0$，则输出为 $1$。如果娜塔莎将输入位 $3$ 改为 $0$，则输出为 $0$。如果娜塔莎将输入位 $6$ 改为 $1$，则输出为 $1$。如果娜塔莎将输入位 $8$ 改为 $0$，则输出为 $1$。如果娜塔莎将输入位 $9$ 改为 $0$，则输出为 $0$。
**Definitions**
Let $ n \in \mathbb{Z} $, $ 2 \leq n \leq 10^6 $, be the number of vertices.
Let $ V = \{1, 2, \dots, n\} $ be the set of vertices, with vertex $ 1 $ as the root (output).
For each vertex $ i \in V $, let $ \text{type}_i \in \{\text{AND}, \text{OR}, \text{XOR}, \text{NOT}, \text{IN}\} $ denote its type.
- If $ \text{type}_i = \text{IN} $, then $ \text{val}_i \in \{0,1\} $ is the initial input bit.
- If $ \text{type}_i \in \{\text{AND}, \text{OR}, \text{XOR}\} $, then $ \text{in}_i = (u_i, v_i) $, where $ u_i, v_i \in V \setminus \{i\} $ are the two children (inputs).
- If $ \text{type}_i = \text{NOT} $, then $ \text{in}_i = (u_i) $, where $ u_i \in V \setminus \{i\} $ is the single child.
Let $ L \subseteq V $ be the set of leaf vertices with $ \text{type}_i = \text{IN} $, excluding the root (if root is IN, but guaranteed root is not IN).
Let $ f: \{0,1\}^{|L|} \to \{0,1\} $ be the Boolean function computed by the circuit, where each input corresponds to a vertex in $ L $, ordered by increasing index.
Let $ \mathbf{b} = (b_j)_{j \in L} \in \{0,1\}^{|L|} $ be the initial input assignment.
For each input vertex $ \ell \in L $, define $ \mathbf{b}^{(\ell)} $ as the modified input vector where $ b_\ell $ is flipped (i.e., $ b_\ell \mapsto 1 - b_\ell $), and all other inputs remain unchanged.
**Constraints**
1. The graph is a tree rooted at vertex $ 1 $.
2. Every non-leaf non-root vertex has exactly one parent.
3. Logical gates have correct arity:
- AND, OR, XOR: exactly two children.
- NOT: exactly one child.
- IN: no children, and only leaves.
4. The root (vertex 1) is not an IN vertex.
5. All child indices are valid and less than $ n $.
**Objective**
For each input vertex $ \ell \in L $, in ascending order of $ \ell $, compute:
$$
f(\mathbf{b}^{(\ell)})
$$
and output a string of length $ |L| $, where the $ i $-th character is $ f(\mathbf{b}^{(\ell_i)}) $, with $ \ell_i $ being the $ i $-th input vertex in increasing index order.