Спільний предок - 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, виведіть у вихідний файл одне число у окремому рядку - відповідь на цей запит.