問題文

$N$ 頂点の有向グラフ $G_S$ があり、頂点には $1$ から $N$ までの番号が付けられています。 $G_S$ には $N-1$ 本の辺があり、$i$ 本目 $(1\\leq i \\leq N-1)$ の辺は頂点 $p_i\\ (1\\leq p_i \\leq i)$ から頂点 $i+1$ に伸びています。

$N$ 頂点の有向グラフ $G$ があり、頂点には $1$ から $N$ までの番号が付けられています。 最初、$G$ は $G_S$ と一致しています。 $G$ に関するクエリが $Q$ 個与えられるので、与えられた順番に処理してください。クエリは次の $2$ 種類のいずれかです。

• 1 u v : $G$ に頂点 $u$ から頂点 $v$ に伸びる辺を追加する。 このとき、以下の条件が満たされることが保証される。
  • $u \\neq v$
  • $G_S$ 上で頂点 $v$ からいくつかの辺を辿ることで頂点 $u$ に到達可能である
• 2 x : $G$ 上で頂点 $x$ からいくつかの辺を辿ることで到達可能な頂点 (頂点 $x$ を含む) のうち、最も番号が小さい頂点の番号を出力する。

制約

• $2\\leq N \\leq 2\\times 10^5$
• $1\\leq Q \\leq 2\\times 10^5$
• $1\\leq p_i\\leq i$
• $1$ 番目の形式のクエリについて、
  • $1\\leq u,v \\leq N$
  • $u \\neq v$
  • $G_S$ 上で頂点 $v$ からいくつかの辺を辿ることで頂点 $u$ に到達可能である
• $2$ 番目の形式のクエリについて、$1\\leq x \\leq N$
• 入力は全て整数

入力

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

$N$ $p_1$ $p_2$ $\\dots$ $p_{N-1}$ $Q$ $\\mathrm{query}_1$ $\\mathrm{query}_2$ $\\vdots$ $\\mathrm{query}_Q$

ただし、$\\mathrm{query}_i$ は $i$ 個目のクエリを表しており、次のいずれかの形式で与えられる。

$1$ $u$ $v$ $2$ $x$

出力

$2$ 番目の形式のクエリの回数を $q$ 回として、$q$ 行出力せよ。 $j\\ (1\\leq j \\leq q)$ 行目には、$2$ 番目の形式のクエリのうち $j$ 個目のものに対する答えを出力せよ。

入力例 1

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

出力例 1

4
2
1

• $1$ 個目のクエリの時点で、$G$ 上で頂点 $4$ からいくつかの辺を辿ることで到達可能な頂点は $4$ のみです。
• $3$ 個目のクエリの時点で、$G$ 上で頂点 $4$ からいくつかの辺を辿ることで到達可能な頂点は $2,3,4, 5$ です。
• $5$ 個目のクエリの時点で、$G$ 上で頂点 $4$ からいくつかの辺を辿ることで到達可能な頂点は $1,2,3,4,5$ です。

入力例 2

7
1 1 2 2 3 3
10
2 5
1 5 2
2 5
1 2 1
1 7 1
1 6 3
2 5
2 6
2 1
1 7 1

出力例 2

5
2
1
1
1