問題文

$N$ 頂点の根付き木が与えられます。頂点には $1$ から $N$ までの番号が振られており、根は頂点 $1$ で、頂点 $i\,(2\leq i\leq N)$ の親は頂点 $P_i$ です。

$Q$ 個の質問が与えられるので答えてください。

$i$ 番目の質問では整数 $X_i, Y_i$ が与えられます。頂点 $X_i$ は頂点 $Y_i$ の祖先であり、二頂点間の距離を $d$ とすると $d\geq2$ です。頂点 $X_i$ と $Y_i$ を結ぶパス上の頂点の番号を順に $v_0,v_1,\ldots,v_d$ （ただし、$v_0=X_i, v_d=Y_i$）とするとき、$v_1$ を出力してください。

制約

• $3\leq N\leq 2\cdot 10^5$
• $1\leq P_i\leq i-1\, (2\leq i\leq N)$
• $1\leq Q\leq 2\cdot 10^5$
• $1\leq X_i,Y_i\leq N\, (1\leq i\leq Q)$
• 頂点 $X_i$ は頂点 $Y_i$ の祖先 $(1\leq i\leq Q)$
• 頂点 $X_i$ と頂点 $Y_i$ の距離は $2$ 以上

入力例 1Copy

7
1 1 3 3 5 5
3
1 7
3 6
3 7

出力例 1Copy

3
5
5

$1$ 番目のクエリにおいて、$(v_0,v_1,v_2,v_3)=(1,3,5,7)$ であり、$v_1=3$ です。

$2$ 番目のクエリにおいて、$(v_0,v_1,v_2)=(3,5,6)$ であり、$v_1=5$ です。

$3$ 番目のクエリにおいて、$(v_0,v_1,v_2)=(3,5,7)$ であり、$v_1=5$ です。

入力例 2Copy

7
1 2 3 4 5 6
5
1 6
2 5
3 7
3 7
1 4

出力例 2Copy

2
3
4
4
2

入力例 3Copy

7
1 1 1 4 3 2
3
1 6
1 7
1 5

出力例 3Copy

3
2
4