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;
typedef pair<int,int> P;
#define MAX_N 100000
int N,M,X,Y;
char a[MAX_N][8];
vector<int> G[MAX_N];

map< vector< int > , int > mp;

int update(char* s,int n){
  int t=X;
  if(s[4]=='Y')t=Y;
  if(s[3]=='&')return n&t;
  if(s[3]=='|')return n|t;
  if(s[3]=='^')return n^t;
}

int rec(int pos,int prev,int depth,int num){
  
  if(prev!=-1){
    num=update(a[pos],num);
    if(G[pos].size()==1) return num;
  }
  
  bool f=depth&1;
  int res=(f?X|Y:0);
  for(int i=0;i<(int)G[pos].size();i++){
    int to=G[pos][i];
    if(to==prev)continue;
    if(f)res=min(res,rec(to,pos,depth+1,num));
    else res=max(res,rec(to,pos,depth+1,num));
  }
  return res;
}

int solve(){
  if(N==1)return 0;
  vector< int> w;
  vector< P > v;
  v.push_back( P(X,0) );
  v.push_back( P(Y,1) );
  v.push_back( P(X|Y,2) );
  v.push_back( P(X&Y,3) );
  v.push_back( P( (X|Y)-X ,4) );
  v.push_back( P( (X|Y)-Y ,5) );
  v.push_back( P( (X|Y)-(X&Y) , 6 ) );
  v.push_back( P( 0 , 7 ) );

  sort(v.begin(),v.end());
  for(int i=0;i<8;i++)w.push_back(v[i].second);
  
  if(mp.count(w)){
    int id=mp[w];
    for(int i=0;i<8;i++)
      if(id==v[i].second)return v[i].first;
  }
  int ans=rec(0,-1,0,0);
  for(int i=0;i<8;i++){
    if(ans==v[i].first)
      mp[w]=v[i].second;
  }
  return ans;
}

int main(){
  scanf("%d %d",&N,&M);
  for(int i=1;i<N;i++)scanf("%s",a[i]);
  for(int i=1;i<N;i++){
    int x,y;
    scanf("%d %d",&x,&y);
    G[x].push_back(y);
    G[y].push_back(x);
  }
  while(M--){
    scanf("%d %d",&X,&Y);
    printf("%d\n",solve());
  }
  return 0;
}