Please note the UNUSUAL MEMORY LIMIT of this problem.

BaoBao has a tree with $n$ vertices. Initially, all edges of the tree are black. BaoBao likes painting and counting in the tree, so he will perform $(n - 1)$ painting operations. For the $i$-th operation, he will paint the $q_i$-th edge red. It’s obvious that after all operations, all edges will become red.

Your task is to calculate how many simple paths in the tree contain exactly $k$ black edges after each operation. Note that we consider the simple path from vertex $u$ to $v$ and from vertex $v$ to $u$ to be the same path.

Recall that a simple path is a path that does not go through the same edge multiple times.

Input

There is only one test case in each test file.

The first line of the input contains two integers $n$ and $k$ ($2 \le n \le 2 \times 10^5$, $1 \le k \le 10$) indicating the number of vertices in the tree and the number of black edges we count for paths.

For the following $(n - 1)$ lines, the $i$-th line contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$) indicating that the $i$-th edge in the tree connects vertices $u_i$ and $v_i$.

For the following $(n - 1)$ lines, the $i$-th line contains an integer $q'_i$ ($1 \le q'_i < n$), indicating the encoded index of the $i$-th edge BaoBao paints. The real value of $q_i$ is equal to $((q'_i + a_{i-1}) \pmod{n - 1}) + 1$, where $a_{i-1}$ is the answer to the $(i - 1)$-th query. Specifically, we define $a_0$ as the number of simple paths in the tree that contain exactly $k$ black edges before BaoBao paints. With the encoded queries, you’re forced to calculate the answer to each query before processing the next one. It’s guaranteed that $q_1, q_2, \dots, q_{n-1}$ is a permutation of $1, 2, \dots, n - 1$.

Output

Output $(n - 1)$ lines where the $i$-th line contains an integer indicating the number of simple paths with exactly $k$ black edges after the $i$-th operation.

Examples

Input 1

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

Output 1

5
7
8
8
0

Input 2

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

Output 2

5
4
2
0
0

Note

For the first sample test case, the real values of $q_1, q_2, q_3, q_4, q_5$ are $5, 3, 4, 1, 2$, respectively. The tree after the first two operations is shown on the left. Black edges are represented with thinner lines, while red edges are represented with thicker lines.

Let $u \to v$ be the simple path from vertex $u$ to $v$. The simple paths containing exactly one black edge are: $1 \to 3, 1 \to 4, 2 \to 3, 2 \to 4, 3 \to 6, 4 \to 6, 5 \to 6$.

For the second sample test case, the real values of $q_1, q_2, q_3, q_4, q_5$ are $3, 1, 5, 2, 4$, respectively. The tree after the first three operations is shown on the right.

The simple paths containing exactly two black edges are: $1 \to 5, 2 \to 5$.