Common Ancestor - 3
A suspended tree is a directed graph that contains no cycles, where each vertex, except for one designated as the root, has exactly one incoming edge. The root of the tree has no incoming edges. In this context, the parent of a vertex is the vertex from which an edge leads to it.
You are given a collection of suspended trees and need to execute the following operations:
0 u v - For two specified vertices u and v, determine if they belong to the same tree. If they do, output their lowest common ancestor (LCA); if not, output 0.
1 u v - Given the root u of one tree and any vertex v from another tree, add an edge from v to u. This operation merges the two trees into a single tree.
These operations must be performed online, meaning each query is revealed only after the previous one has been processed.
Input
The first line of the input contains the integer n, representing the total number of vertices across all trees (1 ≤ n ≤ 50000). The second line provides n integers, each indicating the parent of the corresponding vertex in the initial setup, or 0 if the vertex is a root. The next line contains the integer k, the number of queries (1 ≤ k ≤ 100000). Each of the following k lines contains three integers: the query type (0 for finding the LCA or 1 for adding an edge) and two integers x and y. The vertices involved in the query are determined using the formulas: u = (x - 1 + ans) mod n + 1 and v = (y - 1 + ans) mod n + 1, where ans is the result of the last query of type 0.
Output
For each query of type 0, output the result on a separate line.