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
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define isYES(x) printf("%s\n",(x) ? "YES" : "NO")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define isYes(x) printf("%s\n",(x) ? "Yes" : "No")
#define isIn(x,y,h,w) (x >= 0 && x < h && y >= 0 && y < w)

#define int long long
//using ll = long long;
using P = pair<int,int>;

ostream &operator<<(ostream &os,const P &p){ return os << "(" << p.first << "," << p.second << ")"; }
template<class T>
ostream &operator<<(ostream &os,const vector<T> &v){
	for(int i = 0;i < v.size();i++) os << (i ? "," : "[") << v[i];
	os << "]";
	return os;
}

template<class T> T &chmin(T &a,const T &b){ return a = min(a,b); }
template<class T> T &chmax(T &a,const T &b){ return a = max(a,b); }

const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

string op[100010];
vector<int> G[100010];
int x,y;

int dfs(int v,int d,int t,int prv){
	int ret = d % 2 ? INF : -INF;
	int num = op[v][4] == 'X' ? x : y;
	if(v){
		if(op[v][3] == '&') t &= num;
		else if(op[v][3] == '|') t |= num;
		else t ^= num;
	}
	for(int to : G[v]){
		if(to == prv) continue;
		if(d % 2) chmin(ret,dfs(to,d + 1,t,v));
		else chmax(ret,dfs(to,d + 1,t,v));
	}
	return abs(ret) == INF ? t : ret;
}

signed main(){
	int n,m;
	cin >> n >> m;
	for(int i = 1;i < n;i++) cin >> op[i];
	for(int i = 0;i < n - 1;i++){
		int u,v;
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	map<vector<int>,int> ans;
	vector<int> vec = {1,2,3};
	do{
		x = y = 0;
		for(int i = 0;i < 3;i++){
			x = x * 2 + vec[i] / 2;
			y = y * 2 + vec[i] % 2;
		}
		int t = dfs(0,0,0,-1);
		for(int i = 0;i < 3;i++){
			ans[vec] += (t >> i & 1) << vec[2 - i];
		}
	}while(next_permutation(all(vec)));
	for(int i = 0;i < m;i++){
		cin >> x >> y;
		int ind[4] = {-1,-1,-1,-1},p[20] = {};
		for(int j = 0;j < 20;j++){
			p[j] = (x >> j & 1) * 2 + (y >> j & 1);
			chmax(ind[p[j]],j); 
		}
		vector<int> vec = {1,2,3};
		sort(all(vec),[&](int a,int b){
			return ind[a] > ind[b];
		});
		int a = ans[vec],ret = 0;
		for(int j = 0;j < 20;j++){
			ret += (a >> p[j] & 1) << j;
		}
		cout << ret << endl;
	}
}
