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 N = 1e6 + 7;
struct node {
  int ch[2], val, rnd, siz;
} e[N];
struct note {
  int l, r;
} f[N], ans;
vector<int> v[N];
int n, q, c, k, tot, w[N], lx[N], rx[N], fa[N], ch[N], ft[N], rt[N], gt[N],
    vas[N], len[N], col[N], siz[N], pos[N], pot[N], dfn[N], dft[N], val[N];
inline int read() {
  int num = 0;
  char t = '+', g = getchar();
  while (g < 48 || 57 < g) t = g, g = getchar();
  while (47 < g && g < 58)
    num = (num << 1) + (num << 3) + g - 48, g = getchar();
  if (t == '-') return -num;
  return num;
}
inline bool tmp(int a, int b) { return a > b; }
inline int getnode(int v) {
  k++, e[k].val = v, e[k].rnd = 1ll * rand() * rand() * rand() % 1919810,
       e[k].siz = 1;
  return k;
}
inline int merge(int u, int t) {
  if (!u || !t) return (u + t);
  if (e[u].rnd < e[t].rnd) {
    e[u].ch[1] = merge(e[u].ch[1], t),
    e[u].siz = e[e[u].ch[0]].siz + e[e[u].ch[1]].siz + 1;
    return u;
  } else {
    e[t].ch[0] = merge(u, e[t].ch[0]),
    e[t].siz = e[e[t].ch[0]].siz + e[e[t].ch[1]].siz + 1;
    return t;
  }
}
inline int delet(int u) { return merge(e[u].ch[0], e[u].ch[1]); }
inline void split(int u, int v, int &a, int &b) {
  if (u == 0) return (void)(a = 0, b = 0);
  if (e[u].val <= v)
    a = u, split(e[u].ch[1], v, e[u].ch[1], b);
  else
    b = u, split(e[u].ch[0], v, a, e[u].ch[0]);
  e[u].siz = e[e[u].ch[0]].siz + e[e[u].ch[1]].siz + 1;
}
inline void dfs1(int u) {
  siz[u] = 1;
  for (int i = 0; i < v[u].size(); i++) {
    int x = v[u][i];
    if (fa[u] == x) continue;
    fa[x] = u, dfs1(x), siz[u] += siz[x];
    if (siz[x] > siz[ch[u]]) ch[u] = x;
  }
}
inline void dfs2(int u) {
  if (!ft[u]) ft[u] = u;
  dfn[u] = ++tot, dft[tot] = u;
  gt[ft[u]] = u;
  if (ch[u]) ft[ch[u]] = ft[u], dfs2(ch[u]);
  for (int i = 0; i < v[u].size(); i++) {
    int x = v[u][i];
    if (fa[u] == x || ch[u] == x) continue;
    dfs2(x);
  }
}
inline note merge(note a, note b) {
  if (b.l > a.r) {
    b.r = b.l;
    return b;
  }
  if (b.r < a.l) {
    b.l = b.r;
    return b;
  }
  a.l = max(a.l, b.l), a.r = min(a.r, b.r);
  return a;
}
inline void build(int l, int r, int t) {
  if (l == r) {
    f[t].l = lx[dft[l]], f[t].r = rx[dft[l]], pot[l] = t;
    return;
  }
  int d = (l + r) >> 1;
  build(l, d, t << 1), build(d + 1, r, t << 1 | 1),
      f[t] = merge(f[t << 1 | 1], f[t << 1]);
}
inline void solve(int l, int r, int t, int ql, int qr) {
  if (t == 1) ans.l = -1919810, ans.r = 1919810;
  if (l == ql && r == qr) {
    ans = merge(ans, f[t]);
    return;
  }
  int d = (l + r) >> 1;
  if (d + 1 <= qr) solve(d + 1, r, t << 1 | 1, max(d + 1, ql), qr);
  if (ql <= d) solve(l, d, t << 1, ql, min(qr, d));
}
inline int getval(int u, int k) {
  int ans = -k, res = 0;
  u = rt[u];
  while (u > 0) {
    ans = max(ans, min(res + res + e[e[u].ch[1]].siz * 2 + 2 - k, e[u].val));
    if (res + res + e[e[u].ch[1]].siz * 2 + 2 - k >= e[u].val)
      u = e[u].ch[1];
    else
      res = res + e[e[u].ch[1]].siz + 1, u = e[u].ch[0];
  }
  return ans;
}
inline void dfs3(int u) {
  if (col[u] == 0)
    val[u] = -1919810;
  else if (col[u] == 1)
    val[u] = 1919810;
  for (int i = 0; i < v[u].size(); i++)
    if (v[u][i] != fa[u]) dfs3(v[u][i]);
  w[0] = 0;
  for (int i = 0; i < v[u].size(); i++)
    if (v[u][i] != fa[u]) w[++w[0]] = val[v[u][i]];
  sort(w + 1, w + w[0] + 1, tmp);
  int ans = -w[0];
  for (int i = 1; i <= w[0]; i++) ans = max(ans, min(i + i - w[0], w[i]));
  if (col[u] < 0) val[u] = ans;
  w[0] = 0;
  for (int i = 0; i < v[u].size(); i++)
    if (v[u][i] != fa[u] && v[u][i] != ch[u]) w[++w[0]] = val[v[u][i]];
  sort(w + 1, w + w[0] + 1, tmp);
  ans = -w[0] - 1;
  for (int i = 1; i <= w[0]; i++) ans = max(ans, min(i + i - w[0] - 1, w[i]));
  lx[u] = ans;
  ans = -w[0] + 1;
  for (int i = 1; i <= w[0]; i++) ans = max(ans, min(i + i - w[0] + 1, w[i]));
  rx[u] = ans;
  if (ft[u] == u) {
    int x = rt[fa[u]], a, b;
    split(x, val[u], a, b);
    rt[fa[u]] = merge(merge(a, getnode(val[u])), b), vas[u] = val[u];
  }
  len[u] = w[0], vas[u] = val[u];
  if (col[u] >= 0) lx[u] = rx[u] = val[u];
}
inline int clearx(int u, int c) {
  int x, y, z;
  split(u, c - 1, x, y);
  split(y, c, y, z);
  y = delet(y);
  return merge(merge(x, y), z);
}
inline int pushx(int u, int c) {
  int x, y;
  split(u, c, x, y);
  return merge(merge(x, getnode(c)), y);
}
inline void update(int u, int l, int r) {
  u = pot[dfn[u]];
  f[u].l = l, f[u].r = r, u = u >> 1;
  while (u > 0) {
    f[u] = merge(f[u << 1 | 1], f[u << 1]), u = u >> 1;
  }
}
inline void print(int u) {
  if (e[u].ch[0]) print(e[u].ch[0]);
  cout << e[u].val << ",";
  if (e[u].ch[1]) print(e[u].ch[1]);
}
int main() {
  n = read(), c = read();
  int u, t, op;
  for (int i = 1; i < n; i++)
    u = read(), t = read(), v[u].push_back(t), v[t].push_back(u);
  for (int i = 1; i <= n; i++) col[i] = read();
  dfs1(1), dfs2(1), dfs3(1), build(1, n, 1);
  q = read();
  while (q--) {
    op = read();
    if (op == 1) {
      u = read(), solve(1, n, 1, dfn[u], dfn[gt[ft[u]]]);
      if (c <= ans.l)
        puts("1");
      else
        puts("0");
    }
    if (op == 2) {
      u = read(), col[u] = read();
      if (col[u] == 0)
        val[u] = -1919810;
      else if (col[u] == 1)
        val[u] = 1919810;
      update(u, val[u], val[u]);
      while (u > 0) {
        u = gt[ft[u]];
        solve(1, n, 1, dfn[ft[u]], dfn[u]), u = ft[u];
        if (fa[u] > 0) {
          rt[fa[u]] = clearx(rt[fa[u]], vas[u]);
          rt[fa[u]] = pushx(rt[fa[u]], ans.l), vas[u] = ans.l;
          update(fa[u], getval(fa[u], len[fa[u]] + 1),
                 getval(fa[u], len[fa[u]] - 1));
        }
        u = fa[u];
      }
    }
    if (op == 3) c = read();
  }
}