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<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


enum Type{
	AND,
	OR,
	XOR,
};

enum Which{
	X,
	Y,
};

enum Turn{
	turn_A,
	turn_B,
};

struct Node{
	int parent;
	Type type;
	Which which;
	vector<int> children;
};

struct Info{
	Info(int arg_value,int arg_index){
		value = arg_value;
		index = arg_index;
	}
	bool operator<(const struct Info &arg) const{
		if(value != arg.value){
			return value < arg.value;
		}else{
			return index < arg.index;
		}
	}
	int value,index;
};

int N,M;
map<int,int> MAP;
Node nodes[100001];
Turn next_turn[2] = {turn_B,turn_A};
vector<int> G[100001];

int makeCode(vector<Info> work){

	int ret = 0;
	for(int i = 0; i < 8; i++){
		ret = 10*ret+work[i].index;
	}
	return ret;
}

int recursive(int num_X,int num_Y,int node_id,Turn turn,int number){

	if(node_id != 0){

		int ret,tmp;

		switch(nodes[node_id].which){
		case X:
			tmp = num_X;
			break;
		case Y:
			tmp = num_Y;
			break;
		}

		switch(nodes[node_id].type){
		case AND:
			number = number&tmp;
			break;
		case OR:
			number = number|tmp;
			break;
		case XOR:
			number = number^tmp;
			break;
		}

		if(nodes[node_id].children.size() == 0){ //葉
			return number;
		}

		if(turn == turn_A){
			ret = -BIG_NUM;
		}else{ //turn == trun_B
			ret = BIG_NUM;
		}

		for(int i = 0; i < nodes[node_id].children.size(); i++){
			tmp = recursive(num_X,num_Y,nodes[node_id].children[i],next_turn[turn],number);
			if(turn == turn_A){
				ret = max(ret,tmp);
			}else{
				ret = min(ret,tmp);
			}
		}

		return ret;

	}else{ //node_id == 0 :最初はA

		int ret = 0;

		for(int i = 0; i < nodes[node_id].children.size(); i++){
			ret = max(ret,recursive(num_X,num_Y,nodes[node_id].children[i],next_turn[turn],number));
		}

		return ret;
	}
}

int calc(int num_X,int num_Y){

	vector<Info> work;

	work.push_back(Info(0,0));
	work.push_back(Info(num_X,1));
	work.push_back(Info(num_Y,2));
	work.push_back(Info(num_X&num_Y,3));
	work.push_back(Info(num_X|num_Y,4));
	work.push_back(Info(num_X^num_Y,5));
	work.push_back(Info(num_X^(num_X&num_Y),6));
	work.push_back(Info(num_Y^(num_X&num_Y),7));

	sort(work.begin(),work.end());

	int tmp_code = makeCode(work);

	auto at = MAP.find(tmp_code);
	if(at != MAP.end()){
		for(int i = 0; i < 8; i++){
			if(work[i].index == MAP[tmp_code]){
				return work[i].value;
			}
		}
	}

	int ret = recursive(num_X,num_Y,0,turn_A,0);

	for(int i = 0; i < 8; i++){
		if(work[i].value == ret){
			MAP[tmp_code] = work[i].index;
			return ret;
		}
	}
}

void makeTree(int node_id,int pre_node){

	if(pre_node != -1){
		nodes[node_id].parent = pre_node;
		nodes[pre_node].children.push_back(node_id);
	}
	for(int i = 0; i < G[node_id].size(); i++){
		if(G[node_id][i] == pre_node)continue;
		makeTree(G[node_id][i],node_id);
	}
}

int main(){

	scanf("%d %d",&N,&M);

	char buf[6];

	for(int i = 1; i <= N-1; i++){
		scanf("%s",buf);

		switch(buf[3]){
		case '&':
			nodes[i].type = AND;
			break;
		case '|':
			nodes[i].type = OR;
			break;
		case '^':
			nodes[i].type = XOR;
			break;
		}

		switch(buf[4]){
		case 'X':
			nodes[i].which = X;
			break;
		case 'Y':
			nodes[i].which = Y;
			break;
		}
	}

	int from,to;
	for(int loop = 0; loop < N-1; loop++){
		scanf("%d %d",&from,&to);
		G[from].push_back(to);
		G[to].push_back(from);
	}

	makeTree(0,-1);

	int num_X,num_Y;

	for(int loop = 0; loop < M; loop++){
		scanf("%d %d",&num_X,&num_Y);
		if(N == 1){
			printf("0\n");
			continue;
		}
		printf("%d\n",calc(num_X,num_Y));
	}

	return 0;
}