Ten en cuenta el LÍMITE DE MEMORIA INUSUAL de este problema.

BaoBao tiene un árbol con $n$ vértices. Inicialmente, todas las aristas del árbol son negras. A BaoBao le gusta pintar y contar en el árbol, por lo que realizará $(n - 1)$ operaciones de pintura. En la $i$-ésima operación, pintará de rojo la $q_i$-ésima arista. Es evidente que, después de todas las operaciones, todas las aristas serán rojas.

Tu tarea es calcular cuántos caminos simples del árbol contienen exactamente $k$ aristas negras después de cada operación. Ten en cuenta que consideramos que el camino simple del vértice $u$ al $v$ y el del vértice $v$ al $u$ son el mismo camino.

Recuerda que un camino simple es un camino que no pasa por la misma arista varias veces.

Entrada

Cada archivo de prueba contiene un único caso de prueba.

La primera línea de la entrada contiene dos enteros $n$ y $k$ ($2 \le n \le 2 \times 10^5$, $1 \le k \le 10$), que indican el número de vértices del árbol y el número de aristas negras que contamos en los caminos.

La $i$-ésima de las siguientes $(n - 1)$ líneas contiene dos enteros $u_i$ y $v_i$ ($1 \le u_i, v_i \le n$), que indican que la $i$-ésima arista del árbol conecta los vértices $u_i$ y $v_i$.

La $i$-ésima de las siguientes $(n - 1)$ líneas contiene un entero $q'_i$ ($1 \le q'_i < n$), que indica el índice codificado de la $i$-ésima arista que pinta BaoBao. El valor real de $q_i$ es $((q'_i + a_{i-1}) \bmod (n - 1)) + 1$, donde $a_{i-1}$ es la respuesta a la $(i - 1)$-ésima consulta. En particular, definimos $a_0$ como el número de caminos simples del árbol que contienen exactamente $k$ aristas negras antes de que BaoBao pinte. Con las consultas codificadas, debes calcular la respuesta a cada consulta antes de procesar la siguiente. Se garantiza que $q_1, q_2, \ldots, q_{n-1}$ es una permutación de $1, 2, \ldots, n - 1$.

Salida

Imprime $(n - 1)$ líneas. La $i$-ésima línea debe contener un entero que indique el número de caminos simples con exactamente $k$ aristas negras después de la $i$-ésima operación.

Ejemplos

Entrada 1

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

Salida 1

5
7
8
8
0

Entrada 2

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

Salida 2

5
4
2
0
0

Nota

Para el primer caso de ejemplo, los valores reales de $q_1, q_2, q_3, q_4, q_5$ son $5, 3, 4, 1, 2$, respectivamente. El árbol tras las dos primeras operaciones se muestra a la izquierda. Las aristas negras se representan con líneas más finas y las rojas con líneas más gruesas.

Sea $u \to v$ el camino simple del vértice $u$ al $v$. Los caminos simples que contienen exactamente una arista negra son: $1 \to 3, 1 \to 4, 2 \to 3, 2 \to 4, 3 \to 6, 4 \to 6, 5 \to 6$.

Para el segundo caso de ejemplo, los valores reales de $q_1, q_2, q_3, q_4, q_5$ son $3, 1, 5, 2, 4$, respectivamente. El árbol tras las tres primeras operaciones se muestra a la derecha.

Los caminos simples que contienen exactamente dos aristas negras son: $1 \to 5, 2 \to 5$.