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 <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;

vector<int> E[100000];
using P = pair<char,char>;//ope, X/Y
vector<P> V;

int dfs(int v, int pre, int x, int y, int val, bool ismax){//?????°???????????????????????????
    switch(V[v].first){
        case '&':
            val&=(V[v].second=='X'?x:y);
            break;
        case '|':
            val|=(V[v].second=='X'?x:y);
            break;
        case '^':
            val^=(V[v].second=='X'?x:y);
            break;
        default:
            val=0;
            break;
    }
    int ret;
    if(E[v].size()==1&&v){
        ret=val;
    }else{
        if(ismax){
            ret=-(1<<16);
            for(auto to:E[v]){
                if(to!=pre) ret=max(ret,dfs(to,v,x,y,val,!ismax));
            }
        }else{
            ret=(1<<16);
            for(auto to:E[v]){
                if(to!=pre) ret=min(ret,dfs(to,v,x,y,val,!ismax));
            }
        }
    }
    return ret;
}

int main(){
    int N,M;
    cin>>N>>M;
    V.emplace_back(' ','X');
    for(int i=1;i<N;i++){
        string o;
        cin>>o;
        V.emplace_back(o[3],o[4]);
    }
    for(int i=0;i<N-1;i++){
        int u,v;
        cin>>u>>v;
        E[u].push_back(v);
        E[v].push_back(u);
    }
    int memo[16][16];//[x][y]
    for(int x=0;x<16;x++){
        for(int y=0;y<16;y++){
            memo[x][y]=dfs(0,-1,x,y,0,true);
            // cout<<memo[x][y]<<endl;
        }
    }
    for(int i=0;i<M;i++){
        int X,Y;
        cin>>X>>Y;
        //?????§????????¨A=(0,0),B=(0,1),C=(1,0),D=(1,1)???4??????????????????(A?????\?????????????????????????????????)
        int cnt=3,x=0,y=0;
        int A,B,C,D;
        A=B=C=D=-1;
        for(int j=15;j>=0;j--){
            bool bx,by;
            bx=X&(1<<j);
            by=Y&(1<<j);
            if(!bx&&!by){//A
                if(!~A){
                    A=cnt;
                    cnt--;
                }
            }else if(!bx&&by){//B
                if(!~B){
                    B=cnt;
                    y|=(1<<cnt);
                    cnt--;
                }
            }else if(bx&&!by){//C
                if(!~C){
                    C=cnt;
                    x|=(1<<cnt);
                    cnt--;
                }
            }else{//D
                if(!~D){
                    D=cnt;
                    x|=(1<<cnt);
                    y|=(1<<cnt);
                    cnt--;
                }
            }
        }
        A=!!(memo[x][y]&(1<<A));
        B=!!(memo[x][y]&(1<<B));
        C=!!(memo[x][y]&(1<<C));
        D=!!(memo[x][y]&(1<<D));
        int ans = 0;
        for(int j=0;j<16;j++){
            bool bx,by;
            bx=X&(1<<j);
            by=Y&(1<<j);
            if(!bx&&!by){//A
                ans|=(A<<j);
            }else if(!bx&&by){//B
                ans|=(B<<j);
            }else if(bx&&!by){//C
                ans|=(C<<j);
            }else{//D
                ans|=(D<<j);
            }
        }
        cout<<ans<<endl;
    }
}