Задачи
Общий предок - 3
Общий предок - 3
Подвешенное дерево - это ориентированный граф без циклов, в котором в каждую вершину, кроме одной, называемой корнем ориентированного дерева, входит одно ребро. В корень ориентированного дерева не входит ни одного ребра. Отцом вершины называется вершина, ребро из которой входит в данную (по материалам Wikipedia).
Дан набор подвешенных деревьев. Требуется выполнять следующие операции:
\begin{enumerate}
\item \textbf{0 u v} - Для двух заданных вершин \textbf{u} и \textbf{v} выяснить, лежат ли они в одном дереве. Если это так, вывести вершину, являющуюся их наименьшим общим предком, иначе вывести \textbf{0}.
\item \textbf{1 u v} - Для корня \textbf{u} одного из деревьев и произвольной вершины \textbf{v} другого дерева добавить ребро (\textbf{v}, \textbf{u}). В результате эти два дерева соединятся в одно.
\end{enumerate}
Вам необходимо выполнять все операции \textit{online}, т.е. вы сможете узнать следующий запрос, только выполнив предыдущий.
\InputFile
На первой строке входного файла находится число \textbf{n} - суммарное количество вершин в рассматриваемых деревьях (\textbf{1} ≤ \textbf{n} ≤ \textbf{50000}). На следующей строке расположено \textbf{n} чисел - предок каждой вершины в начальной конфигурации, или \textbf{0}, если соответствующая вершина является корнем. Затем следует число \textbf{k} - количество запросов в вашей программе (\textbf{1} ≤ \textbf{k} ≤ \textbf{100000}). Каждая из следующих строк содержит по три целых числа: вид запроса (\textbf{0} - для поиска LCA или \textbf{1} - для добавления ребра) и два числа \textbf{x}, \textbf{y}. Вершины, участвующие в запросе, можно вычислить по следующим формулам: \textbf{u = (x - 1 + ans) mod n + 1}, \textbf{v = (y - 1 + ans) mod n + 1}, где \textbf{ans} - ответ на последний запрос типа \textbf{0}.
\OutputFile
Для каждого запроса типа \textbf{0}, выведите в выходной файл одно число на отдельной строке - ответ на этот запрос.
Входные данные #1
5 0 0 0 0 0 12 1 5 3 0 2 5 1 4 2 1 1 5 0 1 5 1 3 4 0 1 5 0 3 1 0 4 2 0 1 4 0 5 2 0 4 1
Выходные данные #1
0 5 5 3 2 3 3 2
Входные данные #2
10 0 1 7 8 1 5 5 7 0 1 8 1 9 5 0 6 7 0 10 8 0 1 5 0 2 4 0 2 9 0 9 3 0 10 3
Выходные данные #2
5 5 1 5 7 1 1