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;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);
//const ll mod = 1000000007;
int bits[6][3];
int X[6], Y[6];
int ans[6];
int N, M;
vector<string> S;
vector<int> paths[100000];

int dfs(int idx, int now, int val, int depth, int from) {
    if(now != 0) {
        if(S[now] == "T=T&X") val &= X[idx];
        if(S[now] == "T=T&Y") val &= Y[idx];
        if(S[now] == "T=T|X") val |= X[idx];
        if(S[now] == "T=T|Y") val |= Y[idx];
        if(S[now] == "T=T^X") val ^= X[idx];
        if(S[now] == "T=T^Y") val ^= Y[idx];
    }
    vector<int> v;
    for(auto to : paths[now]) {
        if(to == from) continue;
        v.push_back(dfs(idx, to, val, depth + 1, now));
    }
    if(v.size() == 0) return val;
    sort(v.begin(), v.end());
    if(depth & 1) return v[0];
    else return v.back();
}

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> M;
    S.resize(N);
    for(int i = 1; i < N; i++) {
        cin >> S[i];
    }
    for(int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        paths[u].push_back(v);
        paths[v].push_back(u);
    }
    vector<int> v;
    for(int i = 0; i < 3; i++) {
        v.push_back(1 << i);
    }
    for(int i = 0; i < 6; i++) {
        for(int j = 0; j < 3; j++) {
            bits[i][j] = v[j];
        }
        next_permutation(v.begin(), v.end());
    }
    for(int i = 0; i < 6; i++) {
        X[i] = bits[i][0] | bits[i][1];
        Y[i] = bits[i][0] | bits[i][2];
        ans[i] = dfs(i, 0, 0, 0, -1);
        /*
        cerr << i << ": ";
        for(int j = 0; j < 3; j++) {
            cerr << bits[i][j] << " ";
        }
        cerr << ans[i] << endl;
        */
    }
    while(M--) {
        int x, y;
        cin >> x >> y;
        vector<int> u;
        u.push_back(x & y);
        u.push_back(x & (~y));
        u.push_back(y & (~x));
        //cerr << M << ": " << u[0] << " " << u[1] << " " << u[2] << endl;
        for(int i = 0; i < 6; i++) {
            bool ok = true;
            for(int j = 0; j < 3; j++) {
                for(int k = 0; k < j; k++) {
                    if((u[j] < u[k]) ^ (bits[i][j] < bits[i][k])) ok = false;
                }
            }
            if(!ok) continue;
            //cerr << M << " " << i << " " << ok << endl;
            int ansval = 0;
            for(int j = 0; j < 3; j++) {
                if(bits[i][j] & ans[i]) ansval += u[j];
            }
            cout << ansval << endl;
            break;
        }
    }
    return 0;
}
