Олимпиадный тренинг

Задача . D. Марсоход

Задача

Темы: графы Деревья поиск в глубину и подобное реализация *2000

Наташа передвигалась по Марсу на марсоходе. Но неожиданно он сломался, а именно — логическая схема внутри него. Она представляет собой неориентированное дерево (связный ациклический граф) с корнем в вершине $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' (без кавычек) — ответы на задачу для каждого листка по порядку их сортировки по номеру вершины во входных данных.

Примечание

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

$\text{[math]}$