给定一棵有 $n$ 个顶点的树，顶点编号为 $1, 2, \dots, n$。

令 $f(a, b)$ 为不在顶点 $a$ 和 $b$ 之间路径上的顶点中，编号最小的顶点的编号。

你需要回答 $q$ 个形如 $(u_i, v_i)$ 的查询，求出 $f(u_i, v_i)$ 的值。

输入格式

输入的第一行包含两个整数 $n$ 和 $q$ ($4 \le n \le 10^6, 1 \le q \le 10^6$)。接下来的 $(n-1)$ 行，每行包含两个整数 $a_i, b_i$，表示顶点 $a_i$ 和 $b_i$ 之间的一条边 ($1 \le a_i, b_i \le n$)。接下来的 $q$ 行，每行包含两个整数 $u'_i, v'_i$ ($1 \le u'_i, v'_i \le n$)。

查询按以下方式加密：

• $u_1 = u'_1, v_1 = v'_1$。
• 对于 $i \ge 2$，$u_i = u'_i \oplus f(u_{i-1}, v_{i-1}), v_i = v'_i \oplus f(u_{i-1}, v_{i-1})$。

其中 $\oplus$ 表示按位异或运算。

保证对于所有的 $a, b$，$f(a, b)$ 均有定义。

输出格式

对于每个查询，输出一个整数，即该查询的答案。

样例

样例输入 1

4 1
1 2
1 3
1 4
2 3

样例输出 1

4

样例输入 2

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

样例输出 2

3
1