Initially, there is a tree consisting only of the root (vertex with the number ). You must answer the following queries:
ADD — hang the vertex behind the vertex (it is guaranteed that the vertex already exists).
GET — return LCA of vertices and .
Vertices are numbered from to . We have one tree at a time.
The first line contains the number of queries . The next lines contain the queries themselves. It is guaranteed that the number of queries of each type does not exceed .
For each query of the GET type, print on a separate line one integer — the answer to it.