Yuki has a rooted tree $T$ initially containing only the root node $1$, and a variable $n$, initially $n=1$.

There are $q$ operations of the following $2$ types:

• $1\ u_i\ x_i$: Insert node $n+1$ as the $x_i$-th child of $u_i$. Specifically, if $x_i=0$, insert node $n+1$ as the first child of $u_i$. The relative order of the other children of $u_i$ remains unchanged. Let $s_{u_i}$ be the number of children of $u_i$; it is guaranteed that $1 \le u_i \le n$ and $0 \le x_i \le s_{u_i}$. After this operation, the value of $n$ becomes $n+1$.
• $2\ v_i\ k_i$: Query the parent of node $v_i$ after performing $k_i$ "left-child right-sibling" transformations on tree $T$. A left-child right-sibling transformation is defined as follows: for a node $u$ in tree $T$, the first child of $u$ in the original tree becomes the left child of $u$ in the new tree, and the next sibling of $u$ in the original tree becomes the right child of $u$ in the new tree. It is guaranteed that $2 \le v_i \le n$ and $1 \le k_i \le 10^9$. Note that this operation does not actually perform the $k_i$ transformations on tree $T$; that is, the structure of the tree remains unchanged after this operation.

You need to output the answer for each type $2$ operation.

Input

The first line contains two positive integers $c$ and $T$, representing the test case ID and the number of test cases, respectively. The sample satisfies $c=0$.

Each test case is provided as follows:

• The first line contains a positive integer $q$.
• The next $q$ lines each contain three integers $o_i, u_i, x_i$ or $o_i, v_i, k_i$, following the format described above.

Output

For each type $2$ operation in each test case, output a single integer representing the answer on a new line.

Examples

Input 1

0 2
8
1 1 0
1 2 0
2 3 1
1 3 0
1 1 0
1 4 0
1 4 1
2 7 1
8
1 1 0
2 2 2
2 2 2
1 2 0
2 3 1
1 3 0
1 4 0
2 4 3

Output 1

2
6
1
1
2
3

Note 1

This sample contains two test cases. For the first test case:

• The 1st operation inserts node $2$ as a child of node $1$.
• The 2nd operation inserts node $3$ as a child of node $2$.
• At this point, the tree contains edges $(1, 2)$ and $(2, 3)$. After $1$ left-child right-sibling transformation, the tree remains $(1, 2), (2, 3)$, and the parent of $3$ is $2$.
• After the subsequent $4$ insertion operations, the tree structure is:

• After $1$ left-child right-sibling transformation, the tree structure is:

At this point, the parent of node $7$ is $6$.

Examples 2-7

See irris2.in through irris7.in and their corresponding .ans files.

Constraints

For all test cases, it is guaranteed that:

• $1 \le T \le 3$;
• $1 \le q \le 10^6$;
• $o_i \in \{1,2\}$, $1 \le u_i \le n$, $0 \le x_i \le s_{u_i}$, $2 \le v_i \le n$, $1 \le k_i \le 10^9$.

• Special Property A: For all type $1$ operations, $u_i=1$.
• Special Property B: For all positive integers $i, j$ such that $1\le i < j \le q$, $op_i \le op_j$.
• Special Property C: For all type $1$ operations, $x_i=cnt_{u_i}$.