Problem: You are given a tree of n nodes. The tree is rooted at node 1, which is not considered as a leaf regardless of its degree.

Each leaf of the tree has one of the two colors: red or blue. Leaf node v initially has color s_{v}.

The color of each of the internal nodes (including the root) is determined as follows. 

  * Let b be the number of blue immediate children, and r be the number of red immediate children of a given vertex. 
  * Then the color of this vertex is blue if and only if b - r ≥ k, otherwise red. 



Integer k is a parameter that is same for all the nodes.

You need to handle the following types of queries: 

  * 1 v: print the color of node v; 
  * 2 v c: change the color of leaf v to c (c = 0 means red, c = 1 means blue); 
  * 3 h: update the current value of k to h. 

Input

The first line of the input consists of two integers n and k (2 ≤ n ≤ 10^{5}, -n ≤ k ≤ n) — the number of nodes and the initial parameter k.

Each of the next n - 1 lines contains two integers u and v (1 ≤ u,v ≤ n), denoting that there is an edge between vertices u and v.

The next line consists of n space separated integers — the initial array s (-1 ≤ s_i ≤ 1). s_{i} = 0 means that the color of node i is red. s_{i} = 1 means that the color of node i is blue. s_{i} = -1 means that the node i is not a leaf.

The next line contains an integer q (1 ≤ q ≤ 10^5), the number of queries.

q lines follow, each containing a query in one of the following queries: 

  * 1 v (1 ≤ v ≤ n): print the color of node v; 
  * 2 v c (1 ≤ v ≤ n, c = 0 or c = 1): change the color of leaf v to c (c = 0 means red, c = 1 means blue). It is guaranteed that v is a leaf; 
  * 3 h (-n ≤ h ≤ n): update the current value of k to h. 

Output

For each query of the first type, print 0 if the color of vertex v is red, and 1 otherwise.

Example

Input


5 2
1 2
1 3
2 4
2 5
-1 -1 0 1 0
9
1 1
1 2
3 -2
1 1
1 2
3 1
2 5 1
1 1
1 2


Output


0
0
1
1
0
1

Note

Figures:

(i) The initial tree 

(ii) The tree after the 3rd query 

(iii) The tree after the 7th query 

<image>

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int inf = (int)1.01e9;
const long long infll = (long long)1.01e18;
const long double eps = 1e-9;
const long double pi = acos((long double)-1);
mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x) { return mrand() % x; }
void precalc() {}
const int maxn = (int)1e5 + 5;
int n, k;
vector<int> g[maxn];
int s[maxn];
bool read() {
  if (scanf("%d%d", &n, &k) < 2) {
    return false;
  }
  for (int i = 0; i < n; i++) {
    g[i].clear();
  }
  for (int i = 0; i < n - 1; i++) {
    int v, u;
    scanf("%d%d", &v, &u);
    v--;
    u--;
    g[v].push_back(u);
    g[u].push_back(v);
  }
  for (int i = 0; i < n; i++) {
    scanf("%d", &s[i]);
  }
  return true;
}
int ts[maxn];
int p[maxn];
void dfs0(int v, int pr) {
  ts[v] = 1;
  p[v] = pr;
  for (int i = 0; i < ((int)(g[v]).size()); i++) {
    int u = g[v][i];
    if (u == pr) {
      swap(g[v][i], g[v].back());
      g[v].pop_back();
      i--;
      continue;
    }
    dfs0(u, v);
    ts[v] += ts[u];
    if (ts[u] > ts[g[v][0]]) {
      swap(g[v][0], g[v][i]);
    }
  }
}
int root[maxn];
int ps[maxn], rs[maxn];
int a[maxn];
vector<int> xs[maxn];
int lvs[maxn][2];
pair<int, int> st[4 * maxn];
pair<int, int> calc(const pair<int, int> &l, const pair<int, int> &r) {
  int blue = (l.first < r.first ? l.first : max(r.first, l.second));
  int red = (l.first < r.second ? l.first : max(r.second, l.second));
  return make_pair(blue, red);
}
void buildst(int v, int tl, int tr) {
  if (tl == tr - 1) {
    st[v] = make_pair(-n, -n);
    return;
  }
  int tm = (tl + tr) / 2;
  buildst(2 * v, tl, tm);
  buildst(2 * v + 1, tm, tr);
  st[v] = calc(st[2 * v], st[2 * v + 1]);
}
pair<int, int> get1(int v) {
  if (s[v] == 0) {
    return make_pair(-n, -n);
  }
  if (s[v] == 1) {
    return make_pair(n + 1, n + 1);
  }
  int res[2];
  for (int it = 0; it < 2; it++) {
    int l = -1, r = ((int)(xs[v]).size());
    while (l < r - 1) {
      int m = (l + r) / 2;
      int bal = ((int)(xs[v]).size()) - 2 * m + lvs[v][1] - lvs[v][0] +
                (!it ? 1 : -1);
      if (bal >= xs[v][m]) {
        l = m;
      } else {
        r = m;
      }
    }
    res[it] = ((int)(xs[v]).size()) - 2 * r + lvs[v][1] - lvs[v][0] +
              (!it ? 1 : -1) + 1;
  }
  return make_pair(res[0], res[1]);
}
void update(int v, int tl, int tr, int pos) {
  if (tl == tr - 1) {
    st[v] = get1(a[tl]);
    return;
  }
  int tm = (tl + tr) / 2;
  if (pos < tm) {
    update(2 * v, tl, tm, pos);
  } else {
    update(2 * v + 1, tm, tr, pos);
  }
  st[v] = calc(st[2 * v], st[2 * v + 1]);
}
pair<int, int> get(int v, int tl, int tr, int l, int r) {
  if (l == tl && r == tr) {
    return st[v];
  }
  int tm = (tl + tr) / 2;
  if (r <= tm) {
    return get(2 * v, tl, tm, l, r);
  }
  if (l >= tm) {
    return get(2 * v + 1, tm, tr, l, r);
  }
  return calc(get(2 * v, tl, tm, l, tm), get(2 * v + 1, tm, tr, tm, r));
}
int getX(int v) { return get(1, 0, n, ps[v], rs[root[v]]).first; }
void changeX(int v, int x, int nx) {
  assert(abs(nx - x) <= 2);
  while (x != nx) {
    if (x < nx) {
      int pos = upper_bound(xs[v].begin(), xs[v].end(), x) - xs[v].begin() - 1;
      assert(xs[v][pos] == x);
      xs[v][pos]++;
      x++;
    } else {
      int pos = lower_bound(xs[v].begin(), xs[v].end(), x) - xs[v].begin();
      assert(xs[v][pos] == x);
      xs[v][pos]--;
      x--;
    }
  }
}
void dfs1(int v) {
  xs[v].clear();
  lvs[v][0] = 0;
  lvs[v][1] = 0;
  for (int i = 0; i < ((int)(g[v]).size()); i++) {
    int u = g[v][i];
    dfs1(u);
    if (i) {
      if (s[u] != -1) {
        lvs[v][s[u]]++;
      } else {
        xs[v].push_back(getX(u));
      }
    }
  }
  sort(xs[v].begin(), xs[v].end());
  update(1, 0, n, ps[v]);
}
void solve() {
  dfs0(0, -1);
  for (int s = 0, pos = 0; s < n; s++) {
    if (p[s] != -1 && s == g[p[s]][0]) {
      continue;
    }
    for (int v = s; v != -1; v = (g[v].empty() ? -1 : g[v][0])) {
      ps[v] = pos;
      a[pos++] = v;
      root[v] = s;
    }
    rs[s] = pos;
  }
  buildst(1, 0, n);
  dfs1(0);
  int q;
  scanf("%d", &q);
  for (int qq = 0; qq < q; qq++) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int v;
      scanf("%d", &v);
      v--;
      int x = getX(v);
      printf("%d\n", (int)(k < x));
    } else if (t == 2) {
      int v, c;
      scanf("%d%d", &v, &c);
      v--;
      int was = s[v];
      s[v] = c;
      while (true) {
        int u = root[v];
        int x = getX(u);
        update(1, 0, n, ps[v]);
        if (p[u] == -1) {
          break;
        }
        int nx = getX(u);
        if (s[u] != -1) {
          lvs[p[u]][was]--;
          lvs[p[u]][c]++;
        } else {
          changeX(p[u], x, nx);
        }
        v = p[u];
      }
    } else {
      int h;
      scanf("%d", &h);
      k = h;
    }
  }
}
int main() {
  precalc();
  while (read()) {
    solve();
  }
  return 0;
}