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>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<int>; using VVI = vector<VI>; using VVVI = vector<VVI>;
const int inf=1e9+7;
const ll INF=1LL<<60;
const ll mod=1e9+7;

int n,m;
VVI e(100010);
VVI res(100010);
VI cal(100010,-1);
vector<char> op(100010);
VI val(100010);
VVI power(24,VI(100010,0));

VVI anse(24);

int b[2][4]={{0,0,1,1},{0,1,0,1}};

VI Po(100010,-2);


void dfs(int u,int pa,int stage){
  if(pa>=0){
    if(op[u]=='|'){
      cal[u]=cal[pa]|b[val[u]][stage];
    }
    else if(op[u]=='&'){
      cal[u]=cal[pa]&b[val[u]][stage];
    } 
    else {
      cal[u]=cal[pa]^b[val[u]][stage];
    }
  }
  if(e[u].size()==1&&pa>=0){
    res[u].pb(cal[u]);
  }
  for(int nex:e[u]){
    if(nex==pa) continue;
    dfs(nex,u,stage);
  }
}

void dfs2(int u,int pa,bool depth){
  if(depth==0) Po[u]=-1; //A
  else Po[u]=inf; //B
  for(int nex:e[u]){
    if(nex==pa) continue;
    if(Po[nex]==-2) dfs2(nex,u,!depth);
    if(depth==0) Po[u]=max(Po[u],Po[nex]);
    else Po[u]=min(Po[u],Po[nex]);
  }
}

int main(){
  int i,j;
  cin>>n>>m;
  for(i=1;i<n;i++){
    string s;
    cin>>s;
    op[i]=s[3];
    val[i]=s[4]-'X';
  }
  for(i=0;i<n-1;i++){
    int u,v;
    cin>>u>>v;
    e[u].pb(v);
    e[v].pb(u);
  }
  VI x(m),y(m);
  for(i=0;i<m;i++){
    cin>>x[i]>>y[i];
  }
  for(i=0;i<4;i++) {
    cal=VI(100010,-1);
    cal[0]=0;
    dfs(0,-1,i);
  }
  for(i=0;i<n;i++){
    if(res[i].size()>=1){
      //cout<<i<<endl;
      //cout<<res[i][0]<<" "<<res[i][1]<<" "<<res[i][2]<<" "<<res[i][3]<<endl;
    }
  }

  map <vector<int>,int > mapp;
  vector<int> perm={0,1,2,3};
  int index=0;
  do{
    Po=VI(100010,-2);
    mapp[perm]=index;
    for(i=0;i<n;i++){
      if(res[i].size()==0) continue;
      for(j=0;j<4;j++) power[index][i]+=(1<<perm[j])*res[i][j];
      Po[i]=power[index][i];
    }

    dfs2(0,-1,0);
    int anspow=Po[0];
    int fl;
    for(i=0;i<n;i++){
      if(res[i].size()>0&&Po[i]==anspow) {
        fl=i;
      }
    }
    anse[index]=res[fl];

    index++;
  } while(next_permutation(perm.begin(),perm.end()));

  for(i=0;i<m;i++){
    ll ans=0;
    int ord=3;
    VI cnt(4,0);
    vector<int> f(4);
    for(j=15;j>=0;j--){
      int u=2*((x[i]>>j)&1)+((y[i]>>j)&1);
      if(cnt[u]==0){
        cnt[u]++;
        f[u]=ord;
        ord--;
      }
    }
    for(int u=0;u<4;u++){
        if(cnt[u]==0){
          f[u]=ord;
          ord--;
        }
    }
    int type=mapp[f];
    
    for(j=15;j>=0;j--){
      if(((x[i]>>j)&1)==0&&((y[i]>>j)&1)==0){
        ans+=(anse[type][0])<<j;
      }
      else if(((x[i]>>j)&1)==0&&((y[i]>>j)&1)==1){
        ans+=(anse[type][1])<<j;
      }
      else if(((x[i]>>j&1)&1)==1&&((y[i]>>j)&1)==0){
        ans+=(anse[type][2])<<j;
      }
      else {
        ans+=(anse[type][3])<<j;
      }
    }
    cout<<ans<<endl;
    
  }
}

