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


<image>
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

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
from collections import deque
from itertools import permutations
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def solve():
	(N, M) = map(int, readline().split())
	OP = [0] * N
	ops = ['T=T&X\n', 'T=T&Y\n', 'T=T|X\n', 'T=T|Y\n', 'T=T^X\n', 'T=T^Y\n']
	for i in range(N - 1):
		s = readline()
		OP[i + 1] = ops.index(s)
	G = [[] for i in range(N)]
	for i in range(N - 1):
		(u, v) = map(int, readline().split())
		G[u].append(v)
		G[v].append(u)
	used = [0] * N
	used[0] = 1
	P = [-1] * N
	V = []
	D = [0] * N
	que = deque([0])
	for i in range(N):
		v = que.popleft()
		d = D[v] + 1
		for w in G[v]:
			if used[w]:
				continue
			used[w] = 1
			que.append(w)
			P[w] = v
			D[w] = d
			V.append(w)

	def check(x, y):
		S = [0] * N
		for v in V:
			op = OP[v]
			s = S[P[v]]
			if op & 1:
				if op & 2:
					s |= y
				elif op & 4:
					s ^= y
				else:
					s &= y
			elif op & 2:
				s |= x
			elif op & 4:
				s ^= x
			else:
				s &= x
			S[v] = s
		T = [-1] * N
		for v in reversed(V):
			if T[v] == -1:
				T[v] = S[v]
			p = P[v]
			if D[v] & 1:
				T[p] = max(T[p], T[v]) if T[p] != -1 else T[v]
			else:
				T[p] = min(T[p], T[v]) if T[p] != -1 else T[v]
		return T[0]
	Q = [(1, 1), (1, 0), (0, 1)]
	R = {}
	for ((x0, y0), (x1, y1), (x2, y2)) in permutations(Q):
		x = x0 + x1 * 2 + x2 * 4
		y = y0 + y1 * 2 + y2 * 4
		d = check(x, y)
		d0 = d & 1
		d1 = +(d & 2 > 0)
		d2 = +(d & 4 > 0)
		R[(x0, x1, x2), (y0, y1, y2)] = (d0, d1, d2)
		R[(x1, x2), (y1, y2)] = (d1, d2)
		R[(x2,), (y2,)] = (d2,)
	for i in range(M):
		(x, y) = map(int, readline().split())
		c = 0
		E = {}
		Q = []
		x0 = x
		y0 = y
		while x0 or y0:
			x1 = x0 & 1
			y1 = y0 & 1
			if x1 or y1:
				E[x1, y1] = c
			Q.append((x1, y1))
			x0 >>= 1
			y0 >>= 1
			c += 1
		if not E:
			write('0\n')
			continue
		(*S,) = E.keys()
		S.sort(key=E.__getitem__)
		x1 = tuple((p for (p, q) in S))
		y1 = tuple((q for (p, q) in S))
		d1 = R[x1, y1]
		for (p, q, d) in zip(x1, y1, d1):
			E[p, q] = d
		Q.reverse()
		ans = 0
		for (p, q) in Q:
			if p or q:
				ans = ans << 1 | E[p, q]
			else:
				ans <<= 1
		write('%d\n' % ans)
solve()