Problem: 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

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <utility>
using namespace std;
const int inf = 1e9;

vector<bool> used;
vector<string> op;
vector<vector<int> > adj;
int minmax(int cur, int depth, int val, int x, int y){
	int ret = (depth%2==0)? -inf: inf;
	for(int i=0; i<(int)adj[cur].size(); i++){
		int next = adj[cur][i];
		if(used[next]) continue;
		
		int xy = (op[next][4] == 'X')? x: y;
		int nval;
		if(op[next][3]=='&') nval = val & xy;
		if(op[next][3]=='|') nval = val | xy;
		if(op[next][3]=='^') nval = val ^ xy;
		
		used[cur] = true;
		if(depth%2==0){
			ret = max(ret, minmax(next, depth+1, nval, x, y));
		}else{
			ret = min(ret, minmax(next, depth+1, nval, x, y));
		}
		used[cur] = false;
	}
	if(ret==inf || ret==-inf) ret = val;
	return ret;
}
	
int main(){
	int n,m;
	cin >> n >> m;
	op.resize(n);
	adj.resize(n);
	for(int i=1; i<n; i++) cin >> op[i];
	for(int i=0; i<n-1; i++){
		int u,v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	used = vector<bool>(n, false);
	map<pair<int, int>, int> opt;
	for(int i=0; i<3; i++){
		for(int j=0; j<3; j++){
			if(i==j) continue;
			int k = 3-i-j;
			int x = 1<<i | 1<<k;
			int y = 1<<j | 1<<k;
			opt[make_pair(x, y)] = minmax(0, 0, 0, x, y);
		}
	}
	
	for(int i=0; i<m; i++){
		int x,y;
		cin >> x >> y;
		vector<pair<int,int> > mxy(3);
		mxy[0].first = x -(x&y);
		mxy[1].first = y -(x&y);
		mxy[2].first = x&y;
		for(int j=0; j<3; j++) mxy[j].second = j;
		sort(mxy.begin(), mxy.end());
		
		int nx=0, ny=0;
		for(int j=0; j<3; j++){
			if(mxy[j].second == 0) nx |= 1<<j;
			if(mxy[j].second == 1) ny |= 1<<j;
			if(mxy[j].second == 2){
				nx |= 1<<j;
				ny |= 1<<j;
			}
		}
		int ret = opt[make_pair(nx, ny)];
		
		int ans = 0;
		for(int j=0; j<3; j++){
			if((ret&(1<<j)) != 0) ans |= mxy[j].first;
		}
		cout << ans << endl;
	}
	return 0;
}