Bit Operation Game

H --Bit Operation Game

Given a rooted tree with N vertices. The vertices are numbered from 0 to N − 1, and the 0th vertex represents the root. T = 0 for the root, but for the other vertices

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

One of the operations is written. Here, the operators &, |, ^ mean the bitwise operators and, or, xor, respectively.

Mr. A and Mr. B played the following games M times using this tree. The two start from the root and select the child vertices and proceed alternately, starting from Mr. A and reaching the leaves. The final T value when the operations written in the passed nodes are applied in the order of passing is the score. Mr. B wants to make the score as small as possible, and Mr. A wants to make it large. Given the X and Y values ​​of the M games, output the score for each game when the two make the best choice.

Constraints

• 1 ≤ N ≤ 100000
• 1 ≤ M ≤ 100000
• 0 ≤ X, Y <2 ^ {16}

Input Format

Input is given from standard input in the following format.

N M o_1_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

On the first line, the number of vertices N of the tree and the integer M representing the number of games played are entered. From the 2nd line to the Nth line, the operation written at the 1st ... N-1st vertex is input. In addition, the numbers of the two vertices connected by each side are entered in the N-1 line. Finally, the values ​​of X and Y in M ​​games are entered over M lines.

Output Format

Print the final T value for each game on the M line.

Sample Input 1

6 3 T = T | X T = T | Y T = T | Y T = T ^ Y T = T & X; 0 1 0 2 13 14 twenty five 5 6 3 5 0 0

Sample Output 1

Four 6 0

For X = 5, Y = 6, proceed to vertices 0-> 2-> 5, and T = 5 & 6 = 4. If X = 3, Y = 5, then go to vertices 0-> 1-> 4, and T = 3 ^ 5 = 6. If X = 0, Y = 0, T does not change from 0 no matter where you go

Example

Input

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

Output

4 6 0

inputFormat

outputFormat

output the score for each game when the two make the best choice.

Constraints

• 1 ≤ N ≤ 100000
• 1 ≤ M ≤ 100000
• 0 ≤ X, Y <2 ^ {16}

Input Format

Input is given from standard input in the following format.

N M o_1_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

On the first line, the number of vertices N of the tree and the integer M representing the number of games played are entered. From the 2nd line to the Nth line, the operation written at the 1st ... N-1st vertex is input. In addition, the numbers of the two vertices connected by each side are entered in the N-1 line. Finally, the values ​​of X and Y in M ​​games are entered over M lines.

Output Format

Print the final T value for each game on the M line.

Sample Input 1

6 3 T = T | X T = T | Y T = T | Y T = T ^ Y T = T & X; 0 1 0 2 13 14 twenty five 5 6 3 5 0 0

Sample Output 1

Four 6 0

For X = 5, Y = 6, proceed to vertices 0-> 2-> 5, and T = 5 & 6 = 4. If X = 3, Y = 5, then go to vertices 0-> 1-> 4, and T = 3 ^ 5 = 6. If X = 0, Y = 0, T does not change from 0 no matter where you go

Example

Input

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

Output

4 6 0

样例

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

4
6
0

</p>