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;

map<vector<int>, int> memo;
vector<int> op;
int x, y;

using graph = vector<vector<int>>;

int proc(int now, int op) {
    if(op == 0) {
        return now & x;
    } else if(op == 1) {
        return now & y;
    } else if(op == 2) {
        return now | x;
    } else if(op == 3) {
        return now | y;
    } else if(op == 4) {
        return now ^ x;
    } else {
        return now ^ y;
    }
}

int dfs(int v, graph& g, int prev, int now, int turn) {
    if(g.size() == 1) {
        return 0;
    }
    if(g[v].size() == 1 && prev != -1) {
        return now;
    }
    int res = -1;
    for(auto to : g[v]) {
        if(to == prev) {
            continue;
        }
        int t = dfs(to, g, v, proc(now, op[to]), turn^1);
        if(res == -1) {
            res = t;
            continue;
        }
        if(turn == 0) {
            res = max(res, t);
        } else {
            res = min(res, t);
        }
    }
    return res;
}

int main() {
    int N, M;
    cin >> N >> M;
    op.resize(N);
    for(int i=1; i<N; ++i) {
        string o;
        cin >> o;
        char c1 = o[3], c2 = o[4];
        if(c1 == '&') {
            op[i] = o[4] - 'X';
        } else if(c1 == '|') {
            op[i] = 2 + o[4] - 'X';
        } else {
            op[i] = 4 + o[4] - 'X';
        }
    }
    vector<vector<int>> 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);
    }

    for(int i=0; i<M; ++i) {
        cin >> x >> y;
        vector<pair<int, int>> v(8);
        vector<int> v2(8);
        v[0] = make_pair(0, 0);
        v[1] = make_pair(x, 1);
        v[2] = make_pair(y, 2);
        v[3] = make_pair(x|y, 3);
        v[4] = make_pair(x&y, 4);
        v[5] = make_pair(x^y, 5);
        v[6] = make_pair(x^(x&y), 6);
        v[7] = make_pair(y^(x&y), 7);
        auto v3 = v;
        sort(v.begin(), v.end());
        for(int i=0; i<8; ++i) {
            v2[v[i].second] = i;
        }
        int res = -1;
        if(memo.count(v2) == 0) {
            res = dfs(0, g, -1, 0, 0);
            for(auto& p : v) {
                if(p.first == res) {
                    memo[v2] = p.second;
                }
            }
        } else {
            res = v3[memo[v2]].first;
        }
        cout << res << endl;
    }
}