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 <iostream>
#include <vector>
#define show(x) cerr << #x << " = " << x << endl
using namespace std;
struct Graph {
    Graph(const int n)
    {
        edge.resize(n);
    }
    void addEdge(const int from, const int to)
    {
        edge[from].push_back(to);
        edge[to].push_back(from);
    }
    vector<vector<int>> edge;
};


inline int calc(const int v, const int p)
{
    constexpr int WEIGHT[6][3] = {{1, 2, 4}, {1, 4, 2}, {2, 1, 4}, {2, 4, 1}, {4, 1, 2}, {4, 2, 1}};
    int ans = 0;
    for (int i = 0; i < 3; i++) {
        if (v & (1 << i)) {
            ans += WEIGHT[p][i];
        }
    }
    return ans;
}

inline int next(const int label, const int mask)
{
    switch (label) {
    case 0:
        return mask & 0b101;
    case 1:
        return mask & 0b110;
    case 2:
        return mask | 0b101;
    case 3:
        return mask | 0b110;
    case 4:
        return mask ^ 0b101;
    case 5:
        return mask ^ 0b110;
    default:
        return 0;
    }
}

void dfs(const Graph& g, const int s, const int d, const int mask, const vector<int>& label, vector<bool>& used, vector<vector<int>>& dp)
{
    used[s] = true;
    const int m = next(label[s], mask);
    vector<int> ch;
    for (const int to : g.edge[s]) {
        if (not used[to]) {
            ch.push_back(to);
            dfs(g, to, d + 1, m, label, used, dp);
        }
    }
    if (ch.empty()) {
        for (int i = 0; i < 6; i++) {
            dp[s][i] = m;
        }
    } else {
        for (int i = 0; i < 6; i++) {
            if (d % 2 == 0) {
                int maxi = -1;
                int maxind = 0;
                for (const int to : ch) {
                    const int x = dp[to][i];
                    const int v = calc(x, i);
                    if (maxi < v) {
                        maxi = v;
                        maxind = x;
                    }
                }
                dp[s][i] = maxind;
            } else {
                int mini = 8;
                int minind = 0;
                for (const int to : ch) {
                    const int x = dp[to][i];
                    const int v = calc(x, i);
                    if (mini > v) {
                        mini = v;
                        minind = x;
                    }
                }
                dp[s][i] = minind;
            }
        }
    }
}

inline int order(const int v[3])
{
    if (v[0] < v[1]) {
        if (v[1] < v[2]) {
            return 0;
        } else if (v[0] < v[2]) {
            return 1;
        } else {
            return 3;
        }
    } else {
        if (v[1] > v[2]) {
            return 5;
        } else if (v[0] < v[2]) {
            return 2;
        } else {
            return 4;
        }
    }
}

int main()
{
    const string S[] = {"T=T&X", "T=T&Y", "T=T|X", "T=T|Y", "T=T^X", "T=T^Y"};
    int N, M;
    cin >> N >> M;
    vector<int> label(N, 6);
    for (int i = 1; i < N; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < 6; j++) {
            if (S[j] == s) {
                label[i] = j;
                break;
            }
        }
    }
    Graph g(N);
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        g.addEdge(u, v);
    }
    vector<bool> used(N, false);
    vector<vector<int>> dp(N, vector<int>(6, 0));
    dfs(g, 0, 0, 0, label, used, dp);
    for (int i = 0; i < M; i++) {
        int X, Y;
        cin >> X >> Y;
        int value[3] = {0, 0, 0};
        for (int i = 0; i < 16; i++) {
            const int num = ((X >> i) & 1) + (((Y >> i) & 1) << 1) - 1;
            if (num >= 0) {
                value[num] += 1 << i;
            }
        }
        const int ord = order(value);
        const int mask = dp[0][ord];
        int ans = 0;
        for (int i = 0; i < 3; i++) {
            if (mask & (1 << i)) {
                ans += value[i];
            }
        }
        cout << ans << endl;
    }
    return 0;
}

