LCA: Lowest Common Ancestor

根付き木の２頂点 u, v の共通祖先で最も根から遠い祖先（LCA: Lowest Common Ancestor）を求めよ。

木の節点には 0 を根とする 0 から n-1 までの番号を割りあてる。

入力

n
k0 c1 c2 ... ck0
k1 c1 c2 ... ck1
:
kn-1 c1 c2 ... ckn-1
q
u1 v1
u2 v2
:
uq vq

入力の最初の行に、木の節点の個数 n が与えられる。 続く n 行目に、各節点の情報が与えられる。k_i は節点 i の子の数、c₁, ... c_ki は節点 i の１番目の子の節点番号、... k_i 番目の子の節点番号を示す。

続く行に質問の数 q が与えられる。続く q 行に２つの節点の組 u, v が与えられる。

出力

質問ごとに、u と v の LCA となる節点の番号を１行に出力する

制約

• 1 ≤ n ≤ 100000
• 1 ≤ q ≤ 100000

入力例 1

8
3 1 2 3
2 4 5
0
0
0
2 6 7
0
0
4
4 6
4 7
4 3
5 2

出力例 1

1
1
0
0

---