{"raw_statement":[{"iden":"statement","content":"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.\n\nThere 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.\n\nFor each input, determine what the output will be if Natasha changes this input."},{"iden":"input","content":"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).\n\nThe $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.\n\nIt is guaranteed that input data contains a correct logical scheme with an output produced by the vertex $1$."},{"iden":"output","content":"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."},{"iden":"example","content":"Input\n\n10\nAND 9 4\nIN 1\nIN 1\nXOR 6 5\nAND 3 7\nIN 0\nNOT 10\nIN 1\nIN 1\nAND 2 8\n\nOutput\n\n10110"},{"iden":"note","content":"The original scheme from the example (before the input is changed):\n\n![image](https://espresso.codeforces.com/2f0636d140ebaa2b5cbe6f2d54c27b7add86bf7c.png)\n\nGreen indicates bits _'1'_, yellow indicates bits _'0'_.\n\nIf Natasha changes the input bit $2$ to $0$, then the output will be $1$.\n\nIf Natasha changes the input bit $3$ to $0$, then the output will be $0$.\n\nIf Natasha changes the input bit $6$ to $1$, then the output will be $1$.\n\nIf Natasha changes the input bit $8$ to $0$, then the output will be $1$.\n\nIf Natasha changes the input bit $9$ to $0$, then the output will be $0$."}],"translated_statement":[{"iden":"statement","content":"娜塔莎驾驶火星车在火星上旅行。但突然它坏了——内部的逻辑电路出现了故障。该电路是一个无向树（连通无环图），根节点在顶点 $1$，其中每个叶子节点（除根节点外）都是输入，其余所有顶点都是逻辑元件，包括根节点（作为输出）。每个输入端输入一个比特，输出端返回一个比特。\n\n逻辑元件有四种类型：AND（2个输入）、OR（2个输入）、XOR（2个输入）、NOT（1个输入）。逻辑元件从其直接子节点（输入）获取值，并返回其所执行函数的结果。娜塔莎知道火星车的逻辑电路，并且知道只有一个输入是损坏的。为了修复火星车，她需要改变这个输入的值。\n\n对于每个输入，请确定当娜塔莎改变该输入时，输出的值是多少。\n\n第一行包含一个整数 $n$（$2 lt.eq n lt.eq 10^6$）——图中顶点的数量（包括输入和元件）。\n\n接下来的 $n$ 行中，第 $i$ 行描述第 $i$ 个顶点：第一个单词是 \"AND\"、\"OR\"、\"XOR\"、\"NOT\" 或 \"IN\"（表示该顶点为输入）。如果该顶点是 \"IN\"，则其后跟随该输入的值（0 或 1）；否则，跟随该元件的输入顶点的索引：\"AND\"、\"OR\"、\"XOR\" 有 2 个输入，而 \"NOT\" 有 1 个输入。顶点编号从 1 开始。\n\n保证输入数据构成一个正确的逻辑电路，且输出由顶点 $1$ 产生。\n\n请输出一个由字符 _'0'_ 和 _'1'_ 组成的字符串（不含引号）——按顶点索引升序排列，每个输入改变后对应的输出结果。"},{"iden":"input","content":"第一行包含一个整数 $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$ 产生。"},{"iden":"output","content":"请输出一个由字符 _'0'_ 和 _'1'_ 组成的字符串（不含引号）——按顶点索引升序排列，每个输入改变后对应的输出结果。"},{"iden":"note","content":"示例中的原始电路（在改变输入前）：绿色表示比特 _'1'_，黄色表示比特 _'0'_。如果娜塔莎将输入位 $2$ 改为 $0$，则输出为 $1$。如果娜塔莎将输入位 $3$ 改为 $0$，则输出为 $0$。如果娜塔莎将输入位 $6$ 改为 $1$，则输出为 $1$。如果娜塔莎将输入位 $8$ 改为 $0$，则输出为 $1$。如果娜塔莎将输入位 $9$ 改为 $0$，则输出为 $0$。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 2 \\leq n \\leq 10^6 $, be the number of vertices.  \nLet $ V = \\{1, 2, \\dots, n\\} $ be the set of vertices, with vertex $ 1 $ as the root (output).  \nFor each vertex $ i \\in V $, let $ \\text{type}_i \\in \\{\\text{AND}, \\text{OR}, \\text{XOR}, \\text{NOT}, \\text{IN}\\} $ denote its type.  \n\nLet $ I \\subseteq V $ be the set of input vertices: $ I = \\{ i \\in V \\mid \\text{type}_i = \\text{IN} \\} $.  \nFor each $ i \\in I $, let $ v_i \\in \\{0,1\\} $ be the initial input value.  \n\nLet $ \\text{children}_i \\subseteq V $ denote the set of direct children (inputs) of vertex $ i $:  \n- If $ \\text{type}_i = \\text{AND}, \\text{OR}, \\text{XOR} $, then $ |\\text{children}_i| = 2 $;  \n- If $ \\text{type}_i = \\text{NOT} $, then $ |\\text{children}_i| = 1 $;  \n- If $ \\text{type}_i = \\text{IN} $, then $ \\text{children}_i = \\emptyset $.  \n\nDefine the Boolean function $ f_i: \\{0,1\\}^{|\\text{children}_i|} \\to \\{0,1\\} $ for each non-input vertex $ i $:  \n- $ f_i(x_1, x_2) = x_1 \\land x_2 $ if $ \\text{type}_i = \\text{AND} $,  \n- $ f_i(x_1, x_2) = x_1 \\lor x_2 $ if $ \\text{type}_i = \\text{OR} $,  \n- $ f_i(x_1, x_2) = x_1 \\oplus x_2 $ if $ \\text{type}_i = \\text{XOR} $,  \n- $ f_i(x_1) = \\neg x_1 $ if $ \\text{type}_i = \\text{NOT} $.  \n\nLet $ F: \\{0,1\\}^{|I|} \\to \\{0,1\\} $ be the overall Boolean function computed by the tree, with output at vertex $ 1 $.  \n\n**Constraints**  \n1. The graph is a tree rooted at vertex $ 1 $.  \n2. Every non-input vertex has exactly the number of children as required by its type.  \n3. Input vertices are leaves (excluding root), and the root is not an input.  \n\n**Objective**  \nFor each input vertex $ i \\in I $, in ascending order of index:  \nCompute $ b_i = F(v_1', v_2', \\dots, v_{|I|}') $, where  \n$$\nv_j' = \n\\begin{cases} \n1 - v_j & \\text{if } j = i, \\\\\nv_j & \\text{otherwise}.\n\\end{cases}\n$$  \nOutput the string $ b_1 b_2 \\dots b_{|I|} $, where $ b_i \\in \\{0,1\\} $ is the output of the circuit when input $ i $ is flipped.","simple_statement":null,"has_page_source":false}