读写要求

本题采用文件读写，请在提交代码时使用正确的文件读写方式，否则会导致 RE。

输入：mars.in

输出：mars.out

题目描述

火星车的逻辑电路是一棵以 $1$ 号节点为根的有根树：

• 非根叶子节点是输入节点 IN，每个节点存放一个二进制位（$0$ 或 $1$）；
• 其余节点是逻辑门，包含 AND、OR、XOR、NOT；
• 根节点的计算结果就是整个电路的输出位。

每个逻辑门的输入来自它的直接子节点：

• AND、OR、XOR 有两个输入；
• NOT 有一个输入。

已知当前电路结构与所有输入值。现在假设恰好翻转某一个输入节点（即 $0\leftrightarrow 1$），其余输入不变。

请你对每个输入节点分别回答：若翻转这个输入，电路最终输出会变成什么。

样例对应电路如下图所示：

输入格式

第一行一个整数 $n$（$2 \le n \le 10^6$），表示节点总数。

接下来 $n$ 行描述节点 $1\sim n$：

• 若该节点是输入，格式为：IN x，其中 $x\in\{0,1\}$；
• 若该节点是 NOT，格式为：NOT a；
• 若该节点是 AND、OR 或 XOR，格式为：AND a b、OR a b、XOR a b。

题目保证输入构成合法电路，且根节点为 $1$。

输出格式

按输入节点编号从小到大的顺序，输出一个仅由 0 和 1 组成的字符串。

其中第 $i$ 个字符表示：将对应输入节点翻转后，电路输出的值。

输入输出样例

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

10110

说明/提示

样例中一共有 5 个输入节点，输出字符串长度也为 5。