D. Марсоход
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Наташа передвигалась по Марсу на марсоходе. Но неожиданно он сломался, а именно — логическая схема внутри него. Она представляет собой неориентированное дерево (связный ациклический граф) с корнем в вершине $$$1$$$, в котором листья, не являющиеся корнем — входы, все остальные вершины — логические элементы, в том числе корень — выход. На каждый вход подается один бит. На выходе возвращается один бит.

Логические элементы бывают четырех видов: AND (И, $$$2$$$ входа), OR (ИЛИ, $$$2$$$ входа), XOR (исключающее ИЛИ, $$$2$$$ входа), NOT (НЕ, $$$1$$$ вход). Логические элементы принимают значения со своих прямых потомков (входов) и возвращают результат функции, которую они выполняют. Наташе известна логическая схема марсохода, а также то, что в ней сломался ровно один вход. Чтобы починить марсоход, ей нужно изменить значение на этом входе.

Для каждого входа определите, каким будет результат на выходе, если изменить именно этот вход.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 10^6$$$) — количество вершин графа (входов + элементов).

$$$i$$$-я из следующих $$$n$$$ строк содержит описание $$$i$$$-й вершины: сначала идёт строка "AND", "OR", "XOR", "NOT" или "IN" (означает вход схемы) — тип вершины. Если эта вершина — "IN", то далее написано значение данного входа ($$$0$$$ или $$$1$$$), в противном случае — номера вершин-входов данного элемента: "AND", "OR", "XOR" — $$$2$$$ входа (номера вершин), "NOT" — $$$1$$$ вход (номер вершины). Вершины нумеруются с единицы.

Гарантируется, что во входных данных задана корректная логическая схема с выходом в вершине $$$1$$$.

Выходные данные

Выведите строку из символов '0' и '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
Выходные данные
10110
Примечание

Изначальная схема из тестового примера (до изменения входа):

Зелёным цветом обозначены единичные биты, жёлтым — нулевые.

Если изменить бит на входе $$$2$$$ на $$$0$$$, то на выходе будет $$$1$$$.

Если изменить бит на входе $$$3$$$ на $$$0$$$, то на выходе будет $$$0$$$.

Если изменить бит на входе $$$6$$$ на $$$1$$$, то на выходе будет $$$1$$$.

Если изменить бит на входе $$$8$$$ на $$$0$$$, то на выходе будет $$$1$$$.

Если изменить бит на входе $$$9$$$ на $$$0$$$, то на выходе будет $$$0$$$.