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>
using namespace std;
using Int = long long;

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  
  Int n,m;
  cin>>n>>m;
  
  vector<string> s(n);
  for(Int i=1;i<n;i++) cin>>s[i];
  
  using P = pair<Int, Int>;
  vector<vector<Int> > G(n);
  for(Int i=1;i<n;i++){
    Int u,v;
    cin>>u>>v;
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }

  vector<Int> c(n,0);
  {
    Int x=0b011;
    Int y=0b101;
    vector<Int> w({0,x&y,(x|y)^y,x,(x|y)^x,y,x^y,x|y});
    int cnt=0;
    function<void(Int,Int)> dfs=[&](Int v,Int p){
      cnt++;
      for(Int u:G[v]){
	if(u==p) continue;
	if(s[u]=="T=T&X") c[u]=c[v]&x;
	if(s[u]=="T=T&Y") c[u]=c[v]&y;
	if(s[u]=="T=T|X") c[u]=c[v]|x;
	if(s[u]=="T=T|Y") c[u]=c[v]|y;
	if(s[u]=="T=T^X") c[u]=c[v]^x;
	if(s[u]=="T=T^Y") c[u]=c[v]^y;
	dfs(u,v);
      }
    };
    dfs(0,-1);
    assert(cnt==n);
  }
  
  map<vector<Int>, Int> ans;
  
  for(Int i=0;i<m;i++){
    Int x,y;
    cin>>x>>y;
    vector<Int> w({0,x&y,(x|y)^y,x,(x|y)^x,y,x^y,x|y});
    function<Int(Int,Int,Int)> dfs=[&](Int v,Int p,Int d){
      Int res=-1;
      for(Int u:G[v]){
	if(u==p) continue;
	{
	  if(s[u]=="T=T&X") assert(w[c[u]]==(w[c[v]]&x));
	  if(s[u]=="T=T&Y") assert(w[c[u]]==(w[c[v]]&y));
	  if(s[u]=="T=T|X") assert(w[c[u]]==(w[c[v]]|x));
	  if(s[u]=="T=T|Y") assert(w[c[u]]==(w[c[v]]|y));
	  if(s[u]=="T=T^X") assert(w[c[u]]==(w[c[v]]^x));
	  if(s[u]=="T=T^Y") assert(w[c[u]]==(w[c[v]]^y));
	}
	Int e=dfs(u,v,!d);
	if(res<0) res=e;
	if(!d&&(w[e]>w[res]||(w[e]==w[res]&&e>res))) res=e;
	if( d&&(w[e]<w[res]||(w[e]==w[res]&&e<res))) res=e;
      }
      if(res<0) res=c[v];
      return res;
    };
    
    vector<P> v;
    for(Int i=0;i<8;i++) v.emplace_back(w[i],i);
    sort(v.begin(),v.end());
    vector<Int> u(8);
    for(Int i=0;i<8;i++) u[i]=v[i].second;
    //for(int a:u) cout<<a<<" ";cout<<endl;
    if(!ans.count(u)) ans[u]=dfs(0,-1,0);
    cout<<w[ans[u]]<<endl;
  }
  return 0;
}