問題文

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 以上

入力例 1

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

出力例 1

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 です。

入力例 2

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

出力例 2

2
3
4
4
2

入力例 3

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

出力例 3

3
2
4