娜塔莎乘坐火星探测器绕火星旅行。但突然间它崩溃了,即——它内部的逻辑方案。该方案是一个无向树(连通无环图),根位于顶点$$$1$$$,其中每个叶子(不包括根)都是输入,所有其他顶点都是逻辑元素,包括根,它是输出。每个输入都馈送一位。输出端返回一位。
有四种类型的逻辑元素:AND($$$2$$$ 输入)、OR($$$2$$$ 输入)、XOR($$$2$$$ 输入)、NOT($$$1$$$ 输入)。逻辑元素从其直接后代(输入)获取值并返回它们执行的函数的结果。娜塔莎知道火星探测器的逻辑方案,也知道只有一个输入被破坏。为了修复火星探测器,她需要更改此输入的值。
对于每个输入,确定如果 Natasha 更改此输入,输出将是什么。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^6$$$) - 图中的顶点数(输入和元素)。
接下来的 $$$n$$$ 行的第 $$$i$$$ 包含第 $$$i$$$ 个顶点的描述:第一个单词“AND”、“OR”、“XOR”、“NOT”或“IN”(表示方案的输入)是顶点类型。如果此顶点为“IN”,则遵循此输入的值($$$0$$$ 或 $$$1$$$),否则遵循此元素的输入顶点的索引:“AND”、“OR”、“XOR”有 $$$2$$$ 输入,而“NOT”有 $$$1$$$ 输入。顶点从 1 开始编号。
保证输入数据包含正确的逻辑方案,并由顶点 $$$1$$$ 产生输出。
输出
打印字符串“0”和“1”(不带引号)——按顶点索引升序排列每个输入的问题答案。
示例
输入 #1
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
输出 #1
10110
注意
示例中的原始方案(在输入更改之前):
绿色表示位“1”,黄色表示位“0”。
如果 Natasha 将输入位 $$$2$$$ 更改为 $$$0$$$,则输出将为 $$$1$$$。
如果 Natasha 将输入位 $$$3$$$ 更改为 $$$0$$$,则输出将为 $$$0$$$。
如果 Natasha 将输入位 $$$6$$$ 更改为 $$$1$$$,则输出将为 $$$1$$$。
如果 Natasha 将输入位 $$$8$$$ 更改为 $$$0$$$,则输出将为 $$$1$$$。
如果 Natasha 将输入位 $$$9$$$ 更改为 $$$0$$$,则输出将为 $$$0$$$。