Общий предок - 3
Подвешенное дерево - это ориентированный граф без циклов, в котором в каждую вершину, кроме одной, называемой корнем ориентированного дерева, входит одно ребро. В корень ориентированного дерева не входит ни одного ребра. Отцом вершины называется вершина, ребро из которой входит в данную (по материалам Wikipedia).
Дан набор подвешенных деревьев. Требуется выполнять следующие операции:
0 u v - Для двух заданных вершин u и v выяснить, лежат ли они в одном дереве. Если это так, вывести вершину, являющуюся их наименьшим общим предком, иначе вывести 0.
1 u v - Для корня u одного из деревьев и произвольной вершины v другого дерева добавить ребро (v, u). В результате эти два дерева соединятся в одно.
Вам необходимо выполнять все операции online, т.е. вы сможете узнать следующий запрос, только выполнив предыдущий.
Входные данные
На первой строке входного файла находится число n - суммарное количество вершин в рассматриваемых деревьях (1 ≤ n ≤ 50000). На следующей строке расположено n чисел - предок каждой вершины в начальной конфигурации, или 0, если соответствующая вершина является корнем. Затем следует число k - количество запросов в вашей программе (1 ≤ k ≤ 100000). Каждая из следующих строк содержит по три целых числа: вид запроса (0 - для поиска LCA или 1 - для добавления ребра) и два числа x, y. Вершины, участвующие в запросе, можно вычислить по следующим формулам: u = (x - 1 + ans) mod n + 1, v = (y - 1 + ans) mod n + 1, где ans - ответ на последний запрос типа 0.
Выходные данные
Для каждого запроса типа 0, выведите в выходной файл одно число на отдельной строке - ответ на этот запрос.