Problem: 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

Solution (in CPP):

Solution:
#include "bits/stdc++.h"

using namespace std;

using i64 = long long;

const i64 MOD = i64(1e9) + 7;
const i64 INF = i64(1e18) + 7;


template <typename T>
bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

template <typename T>
bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}

vector<vector<int>> edges;
vector<vector<int>> childs;
vector<int> values;
vector<int> perm;
vector<int> ret;
vector<int> depth;
vector<int> tps;


int g(){
    for(auto x : tps){
        bool maximize = (depth[x] % 2 == 0);
        int rettt = -1;
        for(auto y : childs[x]){
            int ret_idx = ret[y];
            if(rettt == -1)
                rettt = ret_idx;
            else{
                if(maximize && perm[rettt] <= perm[ret_idx])
                    rettt = ret_idx;
                if(!maximize && perm[rettt] >= perm[ret_idx])
                    rettt = ret_idx;
            }
        }
        if(rettt == -1)
            ret[x] = values[x];
        else
            ret[x] = rettt;
    }
    return ret[0];
}

bool solve(){
    int n, m;
    cin >> n >> m;
    vector<string> query(n);
    for(int i = 1; i < n; ++i){
        string s;
        cin >> s;
        query[i] = s.substr(3);
    }
    edges.resize(n);
    childs.resize(n);
    ret.resize(n);
    depth.resize(n, 0);
    for(int i = 0; i < n - 1; ++i){
        int u, v;
        scanf("%d%d", &u, &v);
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    int xx = 0b110;
    int yy = 0b011;
    map<int,int> res_map;
    vector<int> res(8);
    iota(res.begin(), res.end(), 0);
    for(int j = 0; j < 8; ++j)
        res_map[res[j]] = j;

    bitset<100007> visited;
    values.assign(n, 0);
    function<void(int)> f = [&](int x){
        tps.push_back(x);
        for(auto y : edges[x]){
            if(visited[y])
                continue;
            depth[y] = depth[x] + 1;
            childs[x].push_back(y);
            int val = values[x];
            if(query[y] == "&X")
                val = val & xx;
            if(query[y] == "&Y")
                val = val & yy;
            if(query[y] == "|X")
                val = val | xx;
            if(query[y] == "|Y")
                val = val | yy;
            if(query[y] == "^X")
                val = val ^ xx;
            if(query[y] == "^Y")
                val = val ^ yy;
            values[y] = val;
            visited.set(y);
            f(y);
        }
    };
    visited.set(0);
    f(0);

    reverse(tps.begin(), tps.end());

    for(int i = 0; i < n; ++i)
        values[i] = res_map[values[i]];

    map<vector<int>, int> perm_res;

    for(int i = 0; i < m; ++i){
        vector<pair<int,int>> v;
        int x, y;
        scanf("%d%d", &x, &y);
        vector<int> b{~x & y, x & y, x & ~y};
        for(int j = 0; j < 8; ++j){
            int sum = 0;
            for(int k = 0; k < 3; ++k)
                if(j & (1 << k))
                    sum += b[k];
            v.emplace_back(sum, j);
        }
        sort(v.begin(), v.end());
        vector<int> flag(8, 0);
        for(int j = 0; j < 8; ++j){
            flag[v[j].second] = j;
        }

        if(perm_res.find(flag) == perm_res.end()){
            perm = flag;
            perm_res[flag] = g();
        }

        int an = perm_res[flag];
        int ans = 0;
        for(int k = 0; k < 3; ++k)
            if(an & (1 << k))
                ans += b[k];
        printf("%d\n", ans);
    }

    return false;
}

signed main(){
    while(solve());
}