LCA offline (Easy)

Initially, there is a tree consisting only of the root (the vertex with number $1$). You must answer the following queries:

• ADD $ab$ — connect vertex $b$ to vertex $a$ (it is guaranteed that vertex $a$ already exists).

• GET $ab$ — return the LCA (Lowest Common Ancestor) of vertices $a$ and $b$.

Vertices are numbered from $1$ to $n$. There is always exactly one tree.

Output

For each query of type GET, print a single integer — the answer to the corresponding query, on a separate line.