Бинарное дерево — это набор вершин, у каждой из которых может быть левый и правый ребёнок. Одна из вершин является корнем дерева, она не является ребёнком какой-то другой. Начав в корне и каждый раз переходя в одного из детей, можно дойти до любой вершины. Множество вершин, до которых можно дойти из заданной, называется её поддеревом.
У бинарного дерева есть три основных обхода: прямой (pre-order), центрированный (in-order) и обратный (post-order).
Прямой обход дерева — это порядок его вершин, полученный следующим рекурсивным алгоритмом:
-
Добавить корень дерева в обход.
-
Если у корня есть левый ребёнок, выписать прямой обход его поддерева.
-
Если у корня есть правый ребёнок, выписать прямой обход его поддерева.
В центрированном обходе корень дерева выписывается между обходами поддеревьев его детей, в обратном — после обходов поддеревьев его детей.
Обобщим эти три варианта обхода: пусть в каждой вершине записано целое число \(x\) от \(-1\) до \(1\), обозначающее, в какой момент мы выписываем эту вершину, а именно:
-
\(x = -1\): до обходов поддеревьев её детей;
-
\(x = 0\): между обходами поддеревьев её детей;
-
\(x = 1\): после обходов поддеревьев её детей.
Таким образом, если во всех вершинах записано \(-1\), обход является прямым, если \(0\) — центрированным, если \(1\) — обратным.
Рассмотрим дерево с \(n\) вершинами, пронумерованных от \(1\) до \(n\). Корень дерева — вершина \(1\). Изначально во всех вершинах записано число \(-1\).
В рамках исследования необходимо обработать \(q\) запросов одного из следующих типов:
-
Поменять числа в вершинах \(l, l+1, \dots, r\) на \(x\) (\(x\) равен \(-1\), \(0\) или \(1\)).
-
Сообщить, на какой позиции в текущем обходе будет стоять вершина \(i\).
Необходимо вывести ответы на все запросы второго типа.
В первой строке входных данных даны два целых числа \(n\) и \(q\) (\(1 \le n, q \le 100\,000\)).
В следующих \(n\) строках даны по два целых числа \(L_i\) и \(R_i\) (\(0 \le L_i, R_i \le n\)) — номер левого и правого ребёнка вершины \(i\) соответственно, либо \(0\), если соответствующий ребёнок отсутствует.
Гарантируется, что \(L_i\) и \(R_i\) задают корректное бинарное дерево.
Формат входных данных
В следующих \(q\) строках даны запросы. Первое число в строке \(t\) (\(t \in \{1, 2\}\)) — тип запроса.
В случае запроса первого типа далее даны целые числа \(l\), \(r\) и \(x\) (\(1 \le l \le r \le n\), \(x\) равен \(-1\), \(0\) или \(1\)) — границы отрезка вершин, в которых меняются числа, и новое значение.
В случае запроса второго типа далее дано число \(i\) (\(1 \le i \le n\)) — номер вершины, позицию которой в обходе необходимо вывести.
Формат выходных данных
На каждый запрос второго типа выведите единственное число от \(1\) до \(n\) — позицию соответствующей вершины в обходе.
Пусть \(q_1\) — количество запросов первого типа.
В примере обход меняется следующим образом:
-
\([1, 3, 5, 2, 4]\)
-
\([5, 2, 3, 4, 1]\)
-
\([5, 3, 2, 4, 1]\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 5
3 4
0 0
5 2
0 0
0 0
2 2
1 1 3 1
2 5
1 3 3 0
2 3
|
4
1
2
|