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

int n, m, isLeaf[100005], bit[2][2][100005], X, Y;
string s[100005];
vector<int> G[100005];

int cal(int T, string t){
  
  if( t[3] == '&' ){
    if( t[4] == 'X' ) return T & X;
    if( t[4] == 'Y' ) return T & Y;
  }
  
  if( t[3] == '|' ){
    if( t[4] == 'X' ) return T | X;
    if( t[4] == 'Y' ) return T | Y;
  }

  if( t[3] == '^' ){
    if( t[4] == 'X' ) return T ^ X;
    if( t[4] == 'Y' ) return T ^ Y;
  }
  
}

void dfs(int x, int px, int T){
  
  int nT = 0;
  
  if( x != 0 ) nT = cal( T, s[x] );
  
  int flag = 1;
  
  for(int nx : G[x] ){
    
    if( nx == px ) continue;
    
    flag = 0;

    dfs( nx, x, nT );
  }
  
  isLeaf[x] = flag;
  
  bit[X][Y][x] = nT;
  
}

int get(int I, int x){
  if( I == 0 ) return bit[0][1][x];
  if( I == 1 ) return bit[1][0][x];
  return bit[1][1][x];
}

int MM[3][3][3][100005];

int minmax(int x, int px, int dep, int I1, int I2, int I3){
  
  if( isLeaf[x] ){
    
    int res = 0;
    
    res |= get(I1, x);
    res = res << 1;
    res |= get(I2, x);
    res = res << 1;
    res |= get(I3, x);
    
    return MM[I1][I2][I3][x] = res;
  }
  
  int res;
  
  if( dep % 2 == 0 ) res = 0;
  else res = 10;

  for(int nx : G[x] ){
    
    if( nx == px ) continue;
    
    if( dep % 2 == 0 ) res = max( res, minmax( nx, x, dep + 1, I1, I2, I3 ));
    else res = min( res, minmax( nx, x, dep + 1, I1, I2, I3 ));
    
  }  
  
  return MM[I1][I2][I3][x] = res;
}

signed main(){
  
  cin>>n>>m;
  
  for(int i=1;i<n;i++) cin>>s[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);
  }
  
  for(X=0;X<=1;X++){
    
    for(Y=0;Y<=1;Y++){
      
      dfs( 0, -1, 0 );
      
    }
    
  }
  
  minmax( 0, -1, 0, 0, 1, 2 );
  minmax( 0, -1, 0, 0, 2, 1 );
  minmax( 0, -1, 0, 1, 0, 2 );
  minmax( 0, -1, 0, 1, 2, 0 );
  minmax( 0, -1, 0, 2, 0, 1 );
  minmax( 0, -1, 0, 2, 1, 0 );
  
  for(int i=0;i<m;i++){
    
    cin>>X>>Y;
    
    int ans = 0;
    
    int used[3] = {};
    vector<int> pri;
    
    for(int j=16;j>=0;j--){
      
      if( ( ( X >> j ) & 1 ) == 0 && ( Y >>j & 1 ) == 1 ){
	
	if( used[0] ) continue;
	used[0] = 1;
	
	pri.push_back(0);
      }

      if( ( ( X >> j ) & 1 ) == 1 && ( Y >>j & 1 ) == 0 ){
	
	if( used[1] ) continue;
	used[1] = 1;

	pri.push_back(1);
      }

      if( ( ( X >> j ) & 1 ) == 1 && ( Y >>j & 1 ) == 1 ){
	
	if( used[2] ) continue;
	used[2] = 1;

	pri.push_back(2);
      }
      
    }
    
    for(int j=0;j<3;j++)
      if( used[j] == 0 ) pri.push_back(j);
    
    int I1 = pri[0], I2 = pri[1], I3 = pri[2];
    
    for(int j=0;j<17;j++){
      
      if( ( ( X >> j ) & 1 ) == 0 && ( Y >>j & 1 ) == 1 ){
	if( I1 == 0 ) ans |= ( MM[I1][I2][I3][0] >> 2 & 1 ) << j;
	if( I2 == 0 ) ans |= ( MM[I1][I2][I3][0] >> 1 & 1 ) << j;
	if( I3 == 0 ) ans |= ( MM[I1][I2][I3][0] >> 0 & 1 ) << j;
      }
      
      if( ( ( X >> j ) & 1 ) == 1 && ( Y >>j & 1 ) == 0 ){
	if( I1 == 1 ) ans |= ( MM[I1][I2][I3][0] >> 2 & 1 ) << j;
	if( I2 == 1 ) ans |= ( MM[I1][I2][I3][0] >> 1 & 1 ) << j;
	if( I3 == 1 ) ans |= ( MM[I1][I2][I3][0] >> 0 & 1 ) << j;
      }
      
      if( ( ( X >> j ) & 1 ) == 1 && ( Y >>j & 1 ) == 1 ){
	if( I1 == 2 ) ans |= ( MM[I1][I2][I3][0] >> 2 & 1 ) << j;
	if( I2 == 2 ) ans |= ( MM[I1][I2][I3][0] >> 1 & 1 ) << j;
	if( I3 == 2 ) ans |= ( MM[I1][I2][I3][0] >> 0 & 1 ) << j;
      }
            
    }
        
    cout<<ans<<endl;
  }
  
  return 0;
}

