이 문제의 특이한 메모리 제한에 유의하세요.

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}) \bmod (n - 1)) + 1$이며, $a_{i-1}$은 $(i - 1)$번째 질의의 답입니다. 특히 $a_0$는 BaoBao가 색칠하기 전에 트리에서 검은색 간선을 정확히 $k$개 포함하는 단순 경로의 수로 정의합니다. 인코딩된 질의 때문에 다음 질의를 처리하기 전에 각 질의의 답을 계산해야 합니다. $q_1, q_2, \ldots, q_{n-1}$이 $1, 2, \ldots, 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$입니다. 처음 두 번의 연산 후 트리는 왼쪽 그림과 같습니다. 검은색 간선은 가는 선으로, 빨간색 간선은 굵은 선으로 표시되어 있습니다.

정점 $u$에서 $v$로 가는 단순 경로를 $u \to 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$입니다.