Problems
LCA offline
LCA offline
Initially you are given a tree consisting of only one root (the vertex with the number 1). You need to answer the following queries:
ADD a b - hang the vertex b under the vertex a (it is guaranteed that the vertex a already exists).
GET a b - return the LCA of vertices a and b.
The vertices are numbered from 1 to n. At each moment of time you have only one tree.
Input data
The first line contains the number of queries k. Next k lines contains the queries. There is no more than 500000 queries of each type.
Output data
For each query of type GET print in separate line one integer - the answer to the corresponding query.
Examples
Input example #1
9 ADD 1 2 ADD 1 3 ADD 2 4 GET 1 3 GET 2 3 GET 3 4 ADD 2 5 GET 4 5 GET 5 5
Output example #1
1 1 1 2 5