问题描述

给定一棵有 $N$ 个顶点的根树。每个顶点都有从 $0$ 到 $N-1$ 的编号，其中 $0$ 号顶点表示根。根节点上有 T = 0，其他节点上有以下操作之一：

• T=T&X
• T=T&Y
• T=T|X
• T=T|Y
• T=T^X
• T=T^Y

这里的操作符 &、|、^ 分别表示位运算中的与、或、异或。

A 和 B 使用这棵树玩了以下游戏 $M$ 次。两个人从根节点开始，轮流选择子节点进行移动，直到到达叶节点为止。按照经过的节点上的操作，按照顺序应用时，最终的 $T$ 值成为得分。B 希望尽量减小得分，而 A 希望尽量增大得分。给定 M 次游戏中的 X 和 Y 的值，请输出两个人在每个游戏中做出最优选择时的得分。

约束条件

• $1 \leq N \leq 100000$
• $1 \leq M \leq 100000$
• $0 \leq X, Y < 2^{16}$

输入格式

输入以以下格式从标准输入中给出：$N$ $M$ $o_1$ $o_2$ $...$ $o_{N-1}$ $u_1$ $v_1$ $u_2$ $v_2$ $...$ $u_{N-1}$ $v_{N-1}$ $X_1$ $Y_1$ $X_2$ $Y_2$ $...$ $X_M$ $Y_M$

第一行包含树的顶点数 $N$ 和游戏次数 $M$ 的整数。
接下来的 $N-1$ 行中，输入了每个第 $1$ 到第 $N-1$ 号顶点上的操作。
然后，在接下来的 $N-1$ 行中，输入通过每条边连接的 $2$ 个顶点的编号。
最后，按照 $M$ 行输入游戏中 $X$ 和 $Y$ 的值。

输出格式

在每个游戏中，分别输出最终的 $T$ 值，共 $M$ 行。

示例输入 1

6 3
T=T|X
T=T|Y
T=T|Y
T=T^Y
T=T&X
0 1
0 2
1 3
1 4
2 5
5 6
3 5
0 0

示例输出 1

4
6
0