$N$個の頂点からなる木がある。頂点には $1$ から $N$ までの番号が付けられている。辺の重みはすべて $1$ である。

以下のクエリを実行するプログラムを作成せよ。

• k v_1 r_1 v_2 r_2 ... v_k r_k: ある頂点 $x$ が $v_i$ との距離 $r_i$ 以内にあるとき（距離が $r_i$ 以下であるとき）、$x$ は $i$ 番目の条件を満たすとする。木に含まれるすべての頂点のうち、クエリで与えられた $k$ 個の条件のうち $1$ つ以上の条件を満たす頂点の個数を出力せよ。

入力

最初の行に整数 $N$ が与えられる。($1 \le N \le 100{,}000$)

その後 $N-1$ 行には、各辺が接続する二つの頂点番号 $u, v$ が与えられる。($1 \le u, v \le N$)

次の行に整数 $M$ が与えられる。($1 \le M \le 300{,}000$)

その後 $M$ 行に、上で説明したものと同じクエリが与えられる。各クエリは問題文とは異なり、1行では与えられず、$k + 1$ 行に分けて与えられる。入力例を参照せよ。($1 \le v_i \le N$, $0 \le r_i < N$, $1 \le k$)

クエリで与えられる $k$ の合計は $300000$ を超えない。

出力

クエリの結果を1行ずつ出力する。

入出力例

入力例 1

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

出力例 1

10
7