给一棵有 $n$ 个节点的树，初始每个节点上都有一个棋子。

共有 $n-2$ 次操作，每次拿走树上的一个棋子。

请在每次操作后输出最小的任意两个不同棋子的树上距离以及最小距离的点对数量，询问部分强制在线。

输入格式

第一行两个整数 $n,tp$。

接下来 $n-1$ 行每行两个整数 $u,v$ 表示树边 $(u,v)$。

接下来 $n-2$ 行每行一个整数 $x'$ 表示拿走 $x=x'\oplus (lastans\times tp)$ 上的棋子，其中 $\oplus$ 表示异或操作。初始 $lastans=0$，之后表示上一次询问的点对数量。

输出格式

共 $n-2$ 行，每行两个整数表示最短距离和点对数量。

样例 #1

样例输入 #1

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

样例输出 #1

1 2
2 2
4 1

样例 #2

样例输入 #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

样例输出 #2

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

数据范围及约束

对于 $100\%$ 的数据，$2 \leq n \leq 5\times10^5$，$1\le u,v,x\le n$，$x$ 不重复。