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"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
const ld eps = 1e-9;

struct Edge {
	int from;
	int to;
	int id;
	long long int cost;
};

void dfs(const int now,const int from,const vector<vector<int>>&edges, const vector<int>&types,
	vector<int>&nums) {
	for (auto e : edges[now]) {
		if(e==from)continue;
		{
			const int nt=types[e];
			if (nt == 0) {
				nums[e]=nums[now]&0b110;
			}
			else if (nt == 1) {
				nums[e]=nums[now]&0b101;
			}
			else if (nt == 2) {
				nums[e]=nums[now]|0b110;
			}
			else if (nt == 3) {
				nums[e]=nums[now]|0b101;
			}
			else if (nt == 4) {
				nums[e]=nums[now]^0b110;
			}
			else if (nt == 5) {
				nums[e]=nums[now]^0b101;
			}
		}
		dfs(e,now,edges,types,nums);
	}
}

int dfs2(const int now, const int from, const vector<vector<int>>&edges,const vector<int>&types,
	bool is_a,vector<int>&perms) {

	if (edges[now].size() == 1&&from!=-1)return perms[types[now]];
	int ans;
	if (is_a) {
		ans=-1;
	}
	else {
		ans=100;
	}

	for (auto e : edges[now]) {
		if(e==from)continue;
		if (is_a) {
			ans=max(ans,dfs2(e,now,edges,types,!is_a,perms));
		}
		else {
			ans=min(ans,dfs2(e,now,edges,types,!is_a,perms));
		}
	}
	return ans;
}

int main() {
	int N,M;cin>>N>>M;

	map<vector<int>, int>ans_mp;
	
		vector<int>types(N,-1);
		vector<string>name_sts{
			"T=T&X"	 ,
			"T=T&Y" ,
			"T=T|X",
			"T=T|Y",
			"T=T^X",
			"T=T^Y",
		};

		for (int i = 1; i < N; ++i) {
			string st; cin >> st;
			types[i] = find(name_sts.begin(), name_sts.end(), st) - name_sts.begin();
		}

		vector<vector<int>>edges(N);
		for (int i = 0; i < N-1; ++i) {
			int a, b; cin >> a >> b;
			edges[a].push_back(b);
			edges[b].push_back(a);
		}
		vector<int>nums(N);
		dfs(0, -1, edges, types, nums);

		/*vector<int>perms(8);
		iota(perms.begin(),perms.end(),0);
		do {
			bool ok=true;
			for (int i = 1; i < 8; ++i) {
				for (int j = 1; j < 8; ++j) {
					if ((i|j) == j) {
						if (perms[i] > perms[j]) {
							ok = false;
						}
					}
				}
			}
			if(perms[0]<perms[2])
			if(!ok)continue;
			auto num = dfs2(0, -1, edges, nums, true, perms);
			ans_mp[perms] =find(perms.begin(),perms.end(),num)-perms.begin();
		} while (next_permutation(perms.begin() + 1, perms.end() - 1));
*/
	
	
	while (M--) {
		int X,Y;cin>>X>>Y;
		int onlyX=((X|Y)^Y);
		int onlyY=((X|Y)^X);
		vector<pair<int,int>>ps;
		vector<int>anums{
			0,
			onlyY,
			onlyX,
			onlyX|onlyY,
			X&Y,
			Y,
			X,
			X|Y,
		};
		for (int i = 0; i < 8; ++i) {
			ps.emplace_back(anums[i],i);
		}
		sort(ps.begin(),ps.end());
		vector<int>perms(8);
		for (int i = 0; i < 8; ++i) {
			perms[ps[i].second]=i;
		}
		if (ans_mp.find(perms) == ans_mp.end()) {
			auto num= dfs2(0, -1, edges, nums, true, perms);
			ans_mp[perms] =find(perms.begin(),perms.end(),num)-perms.begin();
		}
		int ans_id=ans_mp[perms];
		int ans=anums[ans_id];
		cout<<anums[ans_id]<<endl;
	}
	return 0;
}