LCA offline (Easy)

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

• ADD $ab$ — hang the vertex $b$ behind the vertex $a$ (it is guaranteed that the vertex $a$ already exists).

• GET $ab$ — return LCA of vertices $a$ and $b$.

Vertices are numbered from $1$ to $n$. We have one tree at a time.

Input

The first line contains the number of queries $k$. The next $k$ lines contain the queries themselves. It is guaranteed that the number of queries of each type does not exceed $1000$.

Output

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

Examples