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;

using int64 = long long;

vector< pair< int, int > > beet(int x, int y) {
  vector< pair< int, int > > ret;
  ret.emplace_back(0, 0);
  ret.emplace_back(x, 1);
  ret.emplace_back(y, 2);
  ret.emplace_back(x & y, 3);
  ret.emplace_back(x | y, 4);
  ret.emplace_back(x ^ y, 5);
  ret.emplace_back(x ^ (x & y), 6);
  ret.emplace_back(y ^ (x & y), 7);
  return ret;
}


int N, M;
vector< int > g[100000];
map< vector< pair< int, bool > >, int > dp;
function< int(int, int, int) > fs[100000];

function< int(int, int, int) > getf(string s) {
  if(s == "T=T&X") return [](int t, int x, int y) { return t & x; };
  if(s == "T=T&Y") return [](int t, int x, int y) { return t & y; };
  if(s == "T=T|X") return [](int t, int x, int y) { return t | x; };
  if(s == "T=T|Y") return [](int t, int x, int y) { return t | y; };
  if(s == "T=T^X") return [](int t, int x, int y) { return t ^ x; };
  if(s == "T=T^Y") return [](int t, int x, int y) { return t ^ y; };
  throw 0;
}

int dfs(int idx, int par, int x, int y, int v, bool f) {
  bool leaf = true;
  for(auto &to : g[idx]) if(to != par) leaf = false;
  if(leaf) return v;
  if(f) {
    int ret = 1 << 30;
    for(auto &to : g[idx]) {
      if(to == par) continue;
      ret = min(ret, dfs(to, idx, x, y, fs[to](v, x, y), false));
    }
    return ret;
  } else {
    int ret = -1;
    for(auto &to : g[idx]) {
      if(to == par) continue;
      ret = max(ret, dfs(to, idx, x, y, fs[to](v, x, y), true));
    }
    return ret;
  }
}

int solve(int x, int y) {
  return dfs(0, -1, x, y, 0, false);
}

int main() {
  cin >> N >> M;
  for(int i = 1; i < N; i++) {
    string s;
    cin >> s;
    fs[i] = getf(s);
  }
  for(int i = 1; i < N; i++) {
    int x, y;
    cin >> x >> y;
    g[x].emplace_back(y);
    g[y].emplace_back(x);
  }
  while(M--) {
    int X, Y;
    cin >> X >> Y;
    auto uku = beet(X, Y);
    auto uku2 = uku;
    sort(begin(uku), end(uku));
    vector< pair< int, bool > > state;
    for(int i = 0; i < uku.size(); i++) {
      state.emplace_back(uku[i].second, i > 0 && uku[i - 1].first == uku[i].first);
    }
    if(!dp.count(state)) {
      int ret = solve(X, Y);
      for(int i = 0; i < uku.size(); i++) {
        if(ret == uku[i].first) {
          dp[state] = uku[i].second;
          break;
        }
      }
    }
    cout << uku2[dp[state]].first << endl;
  }
}

