#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;
    }
}