Problem Statement

Yakitori-kun is trying to teach skills to a slime.

There are $N$ skills that the slime can learn, named skill $1, 2, …, N$.

The slime already knows skill $1$. For $2 \leq i \leq N$, in order to learn skill $i$, the slime's level must be at least $L_i$ and the slime must already know skill $A_i$.

You are given $Q$ queries. Process them in order.

Each query is one of the following $2$ types.

• 1 x: Print the maximum number of kinds of skills that a slime of level $x$ can learn.
• 2 y: Print the minimum level required for the slime to learn skill $y$. If skill $y$ cannot be learned, print $-1$.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq L_i \leq 10^9$
• $1 \leq A_i \leq N$
• $A_i \neq i$
• $1 \leq x \leq 10^9$
• $2 \leq y \leq N$
• All inputs are integers.

Input

The input is given from standard input in the following format.

$N$   
$L_2$ $A_2$  
$L_3$ $A_3$  
$\vdots$

$L_N$ $A_N$  
$Q$  
query $1$  
query $2$  
$\vdots$

query $Q$

Each query is given in one of the following $2$ formats.

$1$ $x$

$2$ $y$

Output

Print $Q$ lines.

On the $j \: (1 \leq j \leq Q)$-th line, print the answer to the $j$-th query.

Sample

5
5 1
10 1
8 3
38 4
7
1 1
1 8
1 10
2 2
2 3
2 4
2 5

1
2
4
5
10
10
38

Sample

4
10 4
10 2
10 3
5
1 1
1 10
2 2
2 3
2 4

1
1
-1
-1
-1