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>
#define N 100010
using namespace std;
int n,op[2][N];
vector<int> G[N];

int used[1<<3][1<<3][1<<3][N],mem[1<<3][1<<3][1<<3][N];
int calc(int X,int Y,int T,int pos){
  int XY = op[0][pos]=='X'? X:Y;
  if(op[1][pos] == '|') return T | XY;
  if(op[1][pos] == '&') return T & XY;
  if(op[1][pos] == '^') return T ^ XY;
}

int dfs(int X,int Y,int T=0,int pos=0,int turn=0){
  if(G[pos].empty()) return T;
  if(used[X][Y][T][pos]++) return mem[X][Y][T][pos];
  
  int res = turn==0? 0:7;
  for(int nx:G[pos]) {
    int nT = calc(X,Y,T,nx);
    int r = dfs(X, Y, nT, nx, !turn);
    res = turn==0? max(res,r) : min(res,r);
  }
  return mem[X][Y][T][pos] = res;
}

int main(){
  int m;
  cin>>n>>m;
  
  for(int i=1;i<n;i++){
    string str;
    cin>>str;
    op[0][i] = str[4];
    op[1][i] = str[3];
  }
  
  for(int i=0,a,b;i<n-1;i++)cin>>a>>b,G[a].push_back(b);

  while(m--){
    int X,Y;
    cin>>X>>Y;
    
    int x = 0,y = 0,xy[2][2] = {},cnt=0;
    for(int i=19;i>=0;i--){
      int a = X>>i&1, b = Y>>i&1;
      if(a == 0 && b == 0)continue;
      if(xy[a][b]||cnt++ >= 3) continue;
      xy[a][b] = 3 - cnt;
      x = x*2 + a;
      y = y*2 + b;
    }
    while(cnt++<3) x*=2,y*=2;
    int r = dfs(x,y), ans = 0;
    for(int i=0;i<20;i++) {
      int a = X>>i&1, b = Y>>i&1;
      if(a == 0 && b == 0)continue;
      ans += (r>>xy[a][b]&1)<<i;
    } 
    cout<<ans<<endl;
  }
  return 0;
}