eolymp
bolt
Try our new interface for solving problems
Problems

LCA offline

LCA offline

Time limit 1 second
Memory limit 128 MiB

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