Given a tree with $n$ nodes, initially there is a chess piece on each node.

There are $n-2$ operations in total, where each operation involves removing one chess piece from the tree.

After each operation, output the minimum distance between any two distinct chess pieces on the tree and the number of pairs of pieces that achieve this minimum distance. The queries are forced to be online.

Input

The first line contains two integers $n$ and $tp$.

The next $n-1$ lines each contain two integers $u, v$, representing an edge $(u, v)$ in the tree.

The next $n-2$ lines each contain an integer $x'$, representing the removal of a piece at $x = x' \oplus (lastans \times tp)$, where $\oplus$ denotes the bitwise XOR operation. Initially, $lastans = 0$, and subsequently, $lastans$ represents the number of pairs from the previous query.

Output

There are $n-2$ lines, each containing two integers representing the minimum distance and the number of pairs.

Examples

Input 1

5 0
1 2
2 3
3 4
4 5
2
4
3

Output 1

1 2
2 2
4 1

Input 2

10 1
1 2
1 3
3 4
4 5
5 6
3 7
1 8
6 9
9 10
6
2
1
4
8
2
9
11

Output 2

1 7
1 6
1 5
1 2
1 1
2 1
3 2
3 1

Constraints

For $100\%$ of the data, $2 \leq n \leq 5\times10^5$, $1 \le u, v, x \le n$, and all $x$ are distinct.