Koishi is given a tree $T$, initially rooted at $1$ - the only vertex. She also has $q$ queries, each under the form of 1 in the following 2 types:
- $1$. ```Add x y```: Add a vertex and make $x$ its parent, connected by an edge of weight $y$. Denote $|T|$ as the current size of $T$, then this vertex is numbered $|T| + 1$.
- $2$. ```Query a b```: Find the maximum $XOR$ path from vertex $a$ to any vertex in the subtree rooted at $b$. It is guaranteed that $1 \le x, a, b \le |T|$ for all queries.
Help Koishi find the answer for each query of type $2$.
### Input
- The first line contains an integer $q$.
- The next $q$ lines, each line contains the information of each query.
### Output
- Print the answer for each query of type $2$.
### Constraints
- $1 \le q \le 2 \times 10^5$.
- $1 \le x, a, b \le |T|$.
- $0 \le y \le 2^{30}$.
### Example
Input:
```
4
Add 1 5
Query 1 1
Add 1 7
Query 1 1
```
Output:
```
5
7
```
