BaoBao posiada drzewo o $n$ wierzchołkach. Początkowo wszystkie krawędzie drzewa są czarne. BaoBao lubi malować i liczyć w drzewie, więc wykona $(n - 1)$ operacji malowania. W $i$-tej operacji pomaluje $q_i$-tą krawędź na czerwono. Oczywiste jest, że po wszystkich operacjach wszystkie krawędzie staną się czerwone.

Twoim zadaniem jest obliczenie, ile prostych ścieżek w drzewie zawiera dokładnie $k$ czarnych krawędzi po każdej operacji. Zauważ, że ścieżkę prostą od wierzchołka $u$ do $v$ oraz od wierzchołka $v$ do $u$ traktujemy jako tę samą ścieżkę.

Przypomnijmy, że ścieżka prosta to ścieżka, która nie przechodzi przez tę samą krawędź wielokrotnie.

Wejście

W każdym pliku wejściowym znajduje się tylko jeden zestaw danych.

Pierwsza linia wejścia zawiera dwie liczby całkowite $n$ oraz $k$ ($2 \le n \le 2 \times 10^5$, $1 \le k \le 10$), oznaczające liczbę wierzchołków w drzewie oraz liczbę czarnych krawędzi, które zliczamy na ścieżkach.

W kolejnych $(n - 1)$ liniach, $i$-ta linia zawiera dwie liczby całkowite $u_i$ oraz $v_i$ ($1 \le u_i, v_i \le n$), oznaczające, że $i$-ta krawędź w drzewie łączy wierzchołki $u_i$ oraz $v_i$.

W kolejnych $(n - 1)$ liniach, $i$-ta linia zawiera liczbę całkowitą $q'_i$ ($1 \le q'_i < n$), oznaczającą zakodowany indeks $i$-tej krawędzi, którą maluje BaoBao. Rzeczywista wartość $q_i$ jest równa $((q'_i + a_{i-1}) \pmod{n - 1}) + 1$, gdzie $a_{i-1}$ to odpowiedź na $(i - 1)$-sze zapytanie. W szczególności, definiujemy $a_0$ jako liczbę prostych ścieżek w drzewie, które zawierają dokładnie $k$ czarnych krawędzi przed malowaniem przez BaoBao. Dzięki zakodowanym zapytaniom jesteś zmuszony obliczyć odpowiedź na każde zapytanie przed przetworzeniem następnego. Gwarantuje się, że $q_1, q_2, \dots, q_{n-1}$ jest permutacją liczb $1, 2, \dots, n - 1$.

Wyjście

Wypisz $(n - 1)$ linii, gdzie $i$-ta linia zawiera liczbę całkowitą wskazującą liczbę prostych ścieżek z dokładnie $k$ czarnymi krawędziami po $i$-tej operacji.

Przykład

Wejście 1

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

Wyjście 1

5
7
8
8
0

Wejście 2

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

Wyjście 2

5
4
2
0
0

Uwagi

Dla pierwszego zestawu danych przykładowych, rzeczywiste wartości $q_1, q_2, q_3, q_4, q_5$ to odpowiednio $5, 3, 4, 1, 2$. Drzewo po pierwszych dwóch operacjach pokazano po lewej stronie. Czarne krawędzie przedstawiono cieńszymi liniami, podczas gdy czerwone krawędzie przedstawiono grubszymi liniami.

Niech $u \to v$ oznacza prostą ścieżkę od wierzchołka $u$ do $v$. Proste ścieżki zawierające dokładnie jedną czarną krawędź to: $1 \to 3, 1 \to 4, 2 \to 3, 2 \to 4, 3 \to 6, 4 \to 6, 5 \to 6$.

Dla drugiego zestawu danych przykładowych, rzeczywiste wartości $q_1, q_2, q_3, q_4, q_5$ to odpowiednio $3, 1, 5, 2, 4$. Drzewo po pierwszych trzech operacjach pokazano po prawej stronie.

Proste ścieżki zawierające dokładnie dwie czarne krawędzie to: $1 \to 5, 2 \to 5$.

Drzewo po pierwszych dwóch operacjach pokazano po lewej stronie.