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>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
string s[100001];
int qq[100001];
vector<int> a[100001],check;
vector<pair<int,int> >dig;
#define mk make_pair
map<vector<int>,int>visited;
int n,q,x,y;
void digda(int val,int dep){
  if(!dep)qq[dep]=0;
  else if(s[dep]=="T=T|X")qq[dep]=val|x;
  else if(s[dep]=="T=T|Y")qq[dep]=val|y;
  else if(s[dep]=="T=T^X")qq[dep]=val^x;
  else if(s[dep]=="T=T^Y")qq[dep]=val^y;
  else if(s[dep]=="T=T&X")qq[dep]=val&x;
  else if(s[dep]=="T=T&Y")qq[dep]=val&y;
  r(i,a[dep].size())
    digda(qq[dep],a[dep][i]);
}
void digging(){
  dig.push_back(mk(0,1));
  dig.push_back(mk(x,2));
  dig.push_back(mk(y,3));
  dig.push_back(mk(x^y,4));
  dig.push_back(mk(x&y,5));
  dig.push_back(mk(x|y,6));
  dig.push_back(mk(x^(x&y),7));
  dig.push_back(mk(y^(x&y),8));
}
int diggame(int pl,int turn){
  if(a[pl].size()==0)return qq[pl];
  int res;
  if(turn%2){
    res=1e9;
    r(i,a[pl].size())
      res=min(res,diggame(a[pl][i],turn+1));
  }
  else{
    res=0;
    r(i,a[pl].size())
      res=max(res,diggame(a[pl][i],turn+1));
  }
  return res;
}
int main(){
  cin>>n>>q;
  r(i,n-1)cin>>s[i+1];
  r(i,n-1){
    scanf("%d%d",&x,&y);
    a[x].push_back(y);
  }
  while(q--){
    scanf("%d%d",&x,&y);
    dig.clear();
    check.clear();
    memset(qq,0,sizeof(qq));
    digging();
    sort(dig.begin(),dig.end());
    r(i,8)check.push_back(dig[i].second);
    if(visited[check]){
      int di=visited[check];
      if(di==1)cout<<0<<endl;
      else if(di==2)cout<<x<<endl;
      else if(di==3)cout<<y<<endl;
      else if(di==4)cout<<(x^y)<<endl;
      else if(di==5)cout<<(x&y)<<endl;
      else if(di==6)cout<<(x|y)<<endl;
      else if(di==7)cout<<(x^(x&y))<<endl;
      else if(di==8)cout<<(y^(x&y))<<endl;
    }
    else{
      digda(0,0);
      int p=diggame(0,0);
      cout<<p<<endl;
      r(i,8)if(dig[i].first==p)
        visited[check]=dig[i].second;
    }
  }
}