BaoBaoは $n$ 個の頂点を持つ木を持っています。最初、木のすべての辺は黒色です。BaoBaoは木に対する彩色と計数が好きで、$(n - 1)$ 回の彩色操作を行います。$i$ 回目の操作では、$q_i$ 番目の辺を赤色に塗ります。すべての操作が終わると、すべての辺が赤色になることは明らかです。

各操作の後に、木の中にちょうど $k$ 本の黒い辺を含む単純パスがいくつあるかを計算してください。頂点 $u$ から頂点 $v$ への単純パスと、頂点 $v$ から頂点 $u$ への単純パスは同じものとみなすことに注意してください。

単純パスとは、同じ辺を二度通らないパスのことです。

入力

各テストファイルにはテストケースが1つだけ含まれています。

入力の最初の行には、2つの整数 $n$ と $k$ ($2 \le n \le 2 \times 10^5$, $1 \le k \le 10$) が含まれており、それぞれ木の頂点数と、パスを数える対象となる黒い辺の数を表します。

続く $(n - 1)$ 行には、$i$ 番目の辺が頂点 $u_i$ と $v_i$ を結んでいることを示す2つの整数 $u_i$ と $v_i$ ($1 \le u_i, v_i \le n$) が含まれています。

続く $(n - 1)$ 行には、BaoBaoが塗る $i$ 番目の辺のエンコードされたインデックス $q'_i$ ($1 \le q'_i < n$) が含まれています。$q_i$ の真の値は $((q'_i + a_{i-1}) \pmod{n - 1}) + 1$ であり、$a_{i-1}$ は $(i - 1)$ 回目のクエリに対する答えです。具体的には、$a_0$ をBaoBaoが塗る前に木の中にちょうど $k$ 本の黒い辺を含む単純パスの数と定義します。エンコードされたクエリにより、次のクエリを処理する前に各クエリの答えを計算する必要があります。$q_1, q_2, \dots, q_{n-1}$ は $1, 2, \dots, n - 1$ の順列であることが保証されています。

出力

$(n - 1)$ 行を出力してください。$i$ 行目には、$i$ 回目の操作の後にちょうど $k$ 本の黒い辺を含む単純パスの数を示す整数を出力します。

入出力例

入力 1

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

出力 1

5
7
8
8
0

入力 2

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

出力 2

5
4
2
0
0

注記

最初のサンプルテストケースにおいて、$q_1, q_2, q_3, q_4, q_5$ の真の値はそれぞれ $5, 3, 4, 1, 2$ です。最初の2回の操作後の木を左に示します。黒い辺は細い線で、赤い辺は太い線で表されています。

$u \to v$ を頂点 $u$ から $v$ への単純パスとします。ちょうど1本の黒い辺を含む単純パスは、$1 \to 3, 1 \to 4, 2 \to 3, 2 \to 4, 3 \to 6, 4 \to 6, 5 \to 6$ です。

2番目のサンプルテストケースにおいて、$q_1, q_2, q_3, q_4, q_5$ の真の値はそれぞれ $3, 1, 5, 2, 4$ です。最初の3回の操作後の木を右に示します。

ちょうど2本の黒い辺を含む単純パスは、$1 \to 5, 2 \to 5$ です。