Problem: 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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(x) begin(x),end(x)

using namespace std;

struct Node {
  int op;
  vector<int> children;
  uint8_t state;
};

void dfs(vector<Node> &nodes, int i, uint8_t state = 0) {
  switch (nodes[i].op) {
    case 0:
      state = 0;
      break;
    case 1:
      state |= 3;
      break;
    case 2:
      state |= 5;
      break;
    case 3:
      state &= 3;
      break;
    case 4:
      state &= 5;
      break;
    case 5:
      state ^= 3;
      break;
    case 6:
      state ^= 5;
      break;
  }
  nodes[i].state = state;
  for (int ch : nodes[i].children) {
    dfs(nodes, ch, state);
  }
}

bool solve(const vector<Node> &nodes, int i, uint8_t state, bool player) {
  if (nodes[i].children.empty()) {
    bool valid = (1 << nodes[i].state) & state;
    return valid == player;
  }
  for (int ch : nodes[i].children) {
    if (!solve(nodes, ch, state, !player)) return true;
  }
  return false;
}

int main() {
  int n,m;
  cin>>n>>m;
  vector<Node> nodes(n);
  nodes[0].op = 0;
  REP(i,n-1) {
    string s;
    cin>>s;
    s = s.substr(3);
    if (s == "|X") {
      nodes[i+1].op = 1;
    } else if (s == "|Y") {
      nodes[i+1].op = 2;
    } else if (s == "&X") {
      nodes[i+1].op = 3;
    } else if (s == "&Y") {
      nodes[i+1].op = 4;
    } else if (s == "^X") {
      nodes[i+1].op = 5;
    } else {
      nodes[i+1].op = 6;
    }
  }
  REP(i,n-1) {
    int u,v;
    cin>>u>>v;
    nodes[u].children.push_back(v);
  }
  dfs(nodes, 0);
  vector<bool> vcan(1<<8);
  REP(i,1<<8) {
    vcan[i] = solve(nodes, 0, i, true);
  }
  REP(i,m) {
    int x,y;
    cin>>x>>y;
    vector<pair<int,int>> vp;
    REP(j,8) {
      int val = 0;
      if ((j>>2)&1) val |= y&~x;
      if ((j>>1)&1) val |= x&~y;
      if (j&1) val |= x&y;
      vp.emplace_back(val, j);
    }
    sort(ALL(vp));
    int mx = 0;
    REP(j,1<<8) {
      if (!vcan[j]) continue;
      REP(k,8) {
        if ((j >> vp[k].second) & 1) {
          mx = max(mx, vp[k].first);
          break;
        }
      }
    }
    cout << mx << endl;
  }
  return 0;
}