Initially, there is a tree consisting only of the root (vertex with the number $1$). You must answer the following queries: \begin{itemize} \item \textbf{ADD} $~a~b$ --- hang the vertex $b$ behind the vertex $a$ (it is guaranteed that the vertex $a$ already exists). \item \textbf{GET} $~a~b$ --- return \textbf{LCA} of vertices $a$ and $b$. \end{itemize} Vertices are numbered from $1$ to $n$. We have one tree at a time. \InputFile 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$. \OutputFile For each query of the \textbf{GET} type, print on a separate line one integer --- the answer to it. \includegraphics{https://static.e-olymp.com/content/88/880951afafc2d4d42595b20022206371341a71e8.gif}