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;

long long n, m;
vector<vector<int>> g, perm;
vector<int> memo;
vector<string> o;

vector<int> dfs(int now, int p, int bf = -1, int dep = 0);

int main() {
  {
    vector<int> v = {0, 1, 2, 3};
    do {
      perm.push_back(v);
    } while (next_permutation(v.begin(), v.end()));
  }
  cin >> n >> m;
  o.resize(n);
  g.resize(n);
  memo.assign(24, 0);
  for (int i = 0; i < n - 1; ++i) cin >> o[i + 1];
  for (int i = 0; i < n - 1; ++i) {
    int x, y;
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  memo = dfs(0, 0);
  for (int i = 0; i < m; ++i) {
    int x, y;
    cin >> x >> y;
    int res = 0;
    vector<int> v;
    for (int j = 15; j >= 0; --j) {
      int now = (x >> j & 1) * 2 + (y >> j & 1);
      bool ch = 1;
      for (auto id : v)
        if (id == now) ch = 0;
      if (ch) v.push_back(now);
    }
    int id = -1;
    for (int j = 0; j < 24; ++j) {
      bool ch = 1;
      for (int k = 0; k < v.size(); ++k)
        if (perm[j][k] != v[k]) ch = 0;
      if (ch) id = j;
    }
    for (int j = 0; j < 16; ++j) {
      int now = (x >> j & 1) * 2 + (y >> j & 1);
      if (memo[id] >> now & 1) res += 1 << j;
    }
    cout << res << endl;
  }
  return 0;
}

vector<int> dfs(int now, int p, int bf, int dep) {
  bool ch = 1;
  vector<int> res(24, 0);
  if (bf != -1) {
    int t = 12;
    if (o[now][4] == 'Y') t = 10;
    if (o[now][3] == '&')
      p = p & t;
    else if (o[now][3] == '|')
      p = p | t;
    else
      p = p ^ t;
  }
  for (auto to : g[now])
    if (bf != to) {
      vector<int> tmp = dfs(to, p, now, dep + 1);
      if (ch)
        res = tmp;
      else {
        for (int i = 0; i < 24; ++i) {
          bool ch = 0;
          for (int j = 0; j < 4; ++j) {
            int id = perm[i][j];
            if ((res[i] >> id & 1) != (tmp[i] >> id & 1)) {
              if ((dep & 1) ^ (tmp[i] >> id & 1)) ch = 1;
              break;
            }
          }
          if (ch) res[i] = tmp[i];
        }
      }
      ch = 0;
    }
  if (ch)
    for (int i = 0; i < 24; ++i) res[i] = p;
  return res;
}
