У БаоБао есть дерево с $n$ вершинами. Изначально все ребра дерева черные. БаоБао любит раскрашивать и считать пути в дереве, поэтому он выполнит $(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)$ строк содержат по два целых числа $u_i$ и $v_i$ ($1 \le u_i, v_i \le n$), обозначающих, что $i$-е ребро в дереве соединяет вершины $u_i$ и $v_i$.

Следующие $(n - 1)$ строк содержат по одному целому числу $q'_i$ ($1 \le q'_i < n$), обозначающему закодированный индекс $i$-го ребра, которое красит БаоБао. Реальное значение $q_i$ равно $((q'_i + a_{i-1}) \pmod{n - 1}) + 1$, где $a_{i-1}$ — ответ на $(i - 1)$-й запрос. В частности, мы определяем $a_0$ как количество простых путей в дереве, содержащих ровно $k$ черных ребер до того, как БаоБао начнет красить. Благодаря закодированным запросам вы вынуждены вычислять ответ на каждый запрос перед обработкой следующего. Гарантируется, что $q_1, q_2, \dots, q_{n-1}$ является перестановкой чисел $1, 2, \dots, n - 1$.

Выходные данные

Выведите $(n - 1)$ строк, где $i$-я строка содержит целое число, обозначающее количество простых путей с ровно $k$ черными ребрами после $i$-й операции.

Примеры

Пример 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$.

Дерево после первых двух операций показано слева.