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;
#define int long long
#define REP(i, n) for (int i = 0; i < n; i++)
template <class T> ostream& operator<<(ostream& s, const vector<T>& d) { REP (i, d.size()) s << d[i] << (i == d.size() - 1 ? "" : " "); return s; }

int eval(char c, int a, int b) {
    if (c == '&') return a & b;
    if (c == '|') return a | b;
    if (c == '^') return a ^ b;
    assert(0);
}
signed main() {
    int n, m; cin >> n >> m;
    vector<char> op(n);
    vector<int> var(n);
    REP (i, n - 1) {
        string s; cin >> s;
        op[i + 1] = s[3];
        var[i + 1] = s[4] - 'X';
    }
    vector<vector<int>> g(n);
    REP (i, n - 1) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int> weighted_acc(n);
    function<int(int, int, int, const vector<int>&)> dfs = [&](int v, int prev, int sign, const vector<int>& perm) -> int {
        if (prev != -1 && g[v].size() == 1) return sign * weighted_acc[v];
        int ma = -1e9;
        for (int s : g[v]) if (s != prev) {
            assert(weighted_acc[s] == 0);
            REP (i, 4) {
                int tmp = weighted_acc[v] >> i & 1;
                int x = perm[i] >> 1 & 1;
                int y = perm[i] & 1;
                if (var[s] == 0) tmp = eval(op[s], tmp, x);
                else if (var[s] == 1) tmp = eval(op[s], tmp, y);
                else assert(0);
                weighted_acc[s] |= tmp << i;
            }
            ma = max(ma, - dfs(s, v, -sign, perm));
            assert(abs(ma) < 16);
        }
        return ma;
    };
    map<vector<int>, int> tbl;
    {
        vector<int> perm = {0, 1, 2, 3};
        do {
            tbl[perm] = dfs(0, -1, 1, perm);
            fill(weighted_acc.begin(), weighted_acc.end(), 0);
        } while (next_permutation(perm.begin(), perm.end()));
    }
    REP (_, m) {
        int x, y; cin >> x >> y;
        vector<int> perm, idxs(16);
        for (int k = 15; k >= 0; k--) {
            int idx = (x >> k & 1) << 1 | (y >> k & 1) << 0;
            if (find(perm.begin(), perm.end(), idx) == perm.end()) perm.push_back(idx);
            idxs[k] = idx;
        }
        REP (idx, 4) {
            if (find(perm.begin(), perm.end(), idx) == perm.end()) perm.push_back(idx);
        }
        reverse(perm.begin(), perm.end());
        int tmp = tbl.at(perm);
        int ans = 0;
        REP (k, 16) {
            int shift = find(perm.begin(), perm.end(), idxs[k]) - perm.begin();
            assert(shift < 4);
            ans |= (tmp >> shift & 1) << k;
        }
        cout << ans << endl;
    }
}

