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;

using Graph=vector<vector<int>>;
int main(){
    int n,m;
    cin>>n>>m;
    vector<string> o(n);
    for(int i=1;i<n;i++) cin>>o[i];

    Graph g(n);
    for(int i=0;i<n-1;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    function<int(int,int,int,int,int,int)> game=[&](int v,int pre,int dep,int t,int x,int y){
        if(v==0){
            t=0;
        }
        else{
            int tar=(o[v][4]=='X' ? x : y);
            if(o[v][3]=='&') t&=tar;
            if(o[v][3]=='|') t|=tar;
            if(o[v][3]=='^') t^=tar;
        }
        if(g[v].size()==1 && g[v][0]==pre) return t;
        const int INF=1e9;
        int res=(dep&1) ? INF : 0;
        for(int i=0;i<g[v].size();i++){
            if(g[v][i]!=pre){
                if(dep&1) res=min(res,game(g[v][i],v,dep+1,t,x,y));
                else res=max(res,game(g[v][i],v,dep+1,t,x,y));
            }   
        }
        return res;
    };
    map<pair<int,int>,int> val;
    for(int i=0;i<8;i++){
        for(int j=0;j<8;j++){
            set<pair<int,int>> s;
            bool isok=true;
            for(int k=0;k<3;k++){
                int xb=((i>>k)&1),yb=((j>>k)&1);
                if(xb || yb){
                    isok&=!(s.count(make_pair(xb,yb)));
                    s.insert(make_pair(xb,yb));
                }
            }   
            if(!isok)continue;
            val[make_pair(i,j)]=game(0,0,0,0,i,j);
        }
    }

    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        set<pair<int,int>> s;
        int realx=0,realy=0;
        for(int j=20;j>=0;j--){
            int xb=(x>>j)&1,yb=(y>>j)&1;
            if(xb|yb){
                if(!s.count(make_pair(xb,yb))){
                    s.insert(make_pair(xb,yb));
                    realx<<=1,realy<<=1;
                    realx+=xb,realy+=yb;
                }
            }
        }
        int res=0;
        assert(val.count(make_pair(realx,realy)));
        int tar=val[make_pair(realx,realy)];
        for(int j=0;j<18;j++){
            int xb=(x>>j)&1,yb=(y>>j)&1;
            for(int k=0;k<4;k++){
                if((xb==((realx>>k)&1)) && (yb==((realy>>k)&1))){
                    res+=((tar>>k)&1)<<j;
                    break;
                }
            }
        }
        cout<<res<<endl;
    }
    return 0;
}
