請注意本題有特殊的記憶體限制。

BaoBao 有一棵包含 $n$ 個頂點的樹。起初，樹上的所有邊皆為黑色。BaoBao 喜歡在樹上進行塗色與計數，因此他將執行 $(n - 1)$ 次塗色操作。在第 $i$ 次操作中，他會將第 $q_i$ 條邊塗成紅色。顯然，在所有操作完成後，所有的邊都會變成紅色。

你的任務是計算在每次操作後，樹中有多少條簡單路徑恰好包含 $k$ 條黑色邊。請注意，我們將從頂點 $u$ 到 $v$ 的簡單路徑與從頂點 $v$ 到 $u$ 的簡單路徑視為同一條路徑。

回顧簡單路徑的定義：簡單路徑是指不重複經過同一條邊的路徑。

輸入格式

每個測試檔案僅包含一組測試資料。

第一行包含兩個整數 $n$ 與 $k$ ($2 \le n \le 2 \times 10^5$, $1 \le k \le 10$)，分別代表樹的頂點數量以及我們所要計算的路徑中黑色邊的數量。

接下來的 $(n - 1)$ 行，第 $i$ 行包含兩個整數 $u_i$ 與 $v_i$ ($1 \le u_i, v_i \le n$)，代表樹中的第 $i$ 條邊連接頂點 $u_i$ 與 $v_i$。

接下來的 $(n - 1)$ 行，第 $i$ 行包含一個整數 $q'_i$ ($1 \le q'_i < n$)，代表 BaoBao 所塗色的第 $i$ 條邊的編碼索引。$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

5
7
8
8
0

範例 2

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

5
4
2
0
0

說明

對於第一個範例測試資料，$q_1, q_2, q_3, q_4, q_5$ 的真實值分別為 $5, 3, 4, 1, 2$。左圖顯示了前兩次操作後的樹。黑色邊以較細的線條表示，紅色邊以較粗的線條表示。

令 $u \to v$ 為從頂點 $u$ 到 $v$ 的簡單路徑。恰好包含一條黑色邊的簡單路徑有：$1 \to 3, 1 \to 4, 2 \to 3, 2 \to 4, 3 \to 6, 4 \to 6, 5 \to 6$。

對於第二個範例測試資料，$q_1, q_2, q_3, q_4, q_5$ 的真實值分別為 $3, 1, 5, 2, 4$。右圖顯示了前三次操作後的樹。

恰好包含兩條黑色邊的簡單路徑有：$1 \to 5, 2 \to 5$。