Initially, there is a tree consisting only of the root (vertex with the number 1). You must answer the following queries:
ADD a b — hang the vertex b behind the vertex a (it is guaranteed that the vertex a already exists).
GET a b — return LCA of vertices a and b.
Vertices are numbered from 1 to n. We have one tree at a time.
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.
For each query of the GET type, print on a separate line one integer — the answer to it.