Competitions

# ADA University - February 12 - LCA

# 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

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

For each query of type **GET** print in separate line one integer - the answer to the corresponding query.

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