問題文

やきとりくんは、スライムに技を覚えさせようとしています。

スライムが覚えられる技は $N$ 個あり、技 $1, 2, …, N$ と名前がついています。

スライムは既に技 $1$ を覚えており、$2 \leq i \leq N$ について、技 $i$ を覚えるにはスライムのレベルが $L_i$ 以上 かつ 技 $A_i$ を覚えている必要があります。

$Q$ 個のクエリが与えられるので、順番に処理してください。

クエリは次の $2$ 種類のいずれかです。

• 1 x: レベル $x$ のスライムが覚えられる技の種類数の最大値を出力する。
• 2 y: スライムが技 $y$ を覚えるために必要なレベルの最小値を出力する。技 $y$ を覚えることができない場合には $-1$ を出力する。

制約

• $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$
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

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

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

query $Q$

各クエリは以下に示す $2$ つの形式のいずれかが与えられる。

$1$ $x$

$2$ $y$

出力

$Q$ 行出力せよ。

$j \: (1 \leq j \leq Q)$ 行目では $j$ 番目のクエリに対する答えを出力せよ。

サンプル

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

サンプル

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

1
1
-1
-1
-1