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;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
  return (f == 1) ? x : -x;
}
const int maxn = 100005;
const int maxnode = 2000005;
const int inf = 0x3f3f3f3f;
int n, m, k, col[maxn], lim[maxn], head[maxn], to[maxn << 1], nxt[maxn << 1],
    tot, rt[maxn], sz, rub[maxnode], cnt;
int top[maxn], dep[maxn], siz[maxn], son[maxn], fa[maxn], id[maxn], mp[maxn],
    ed[maxn], tim;
struct node {
  int lc, rc, pri, siz, val;
} t[maxnode];
inline int newnode(int v) {
  int x = cnt ? rub[cnt--] : ++sz;
  t[x].lc = t[x].rc = 0, t[x].pri = rand(), t[x].siz = 1, t[x].val = v;
  return x;
}
void split(int x, int &a, int &b, int v) {
  if (!x) {
    a = b = 0;
    return;
  }
  if (t[x].val <= v)
    a = x, split(t[x].rc, t[a].rc, b, v);
  else
    b = x, split(t[x].lc, a, t[b].lc, v);
  (t[(x)].siz = t[t[(x)].lc].siz + t[t[(x)].rc].siz + 1);
}
void merge(int &x, int a, int b) {
  if (!a || !b) {
    x = a | b;
    return;
  }
  if (t[a].pri < t[b].pri)
    x = a, merge(t[x].rc, t[a].rc, b);
  else
    x = b, merge(t[x].lc, a, t[b].lc);
  (t[(x)].siz = t[t[(x)].lc].siz + t[t[(x)].rc].siz + 1);
}
inline int getrank(int &rt, int v) {
  int x = 0, y = 0, z = 0;
  split(rt, x, y, v);
  z = t[x].siz;
  merge(rt, x, y);
  return z;
}
inline void erase(int &rt, int v) {
  int x = 0, y = 0, z = 0;
  split(rt, x, y, v);
  split(x, x, z, v - 1);
  rub[++cnt] = z;
  merge(z, t[z].lc, t[z].rc);
  merge(x, x, z);
  merge(rt, x, y);
}
inline void insert(int &rt, int v) {
  int x = 0, y = 0, z = newnode(v);
  split(rt, x, y, v);
  merge(x, x, z);
  merge(rt, x, y);
}
struct data {
  int l, r;
  data(int l_ = 0, int r_ = 0) : l(l_), r(r_) {}
} sum[maxn << 2];
inline data operator+(const data &a, const data &b) {
  return data(min(a.r, max(a.l, b.l)), max(a.l, min(a.r, b.r)));
}
inline bool check(int x, int v, int fl) {
  int r = getrank(rt[x], v) + fl, b = t[rt[x]].siz + 1 - r;
  return b - r < v;
}
inline void change(int x, int &v, int fl) {
  while (check(x, v - 1, fl)) v--;
  while (!check(x, v, fl)) v++;
}
void modify(int rt, int l, int r, int x) {
  if (l == r) {
    x = mp[x];
    if (col[x] >= 0)
      sum[rt] = (col[x] == 0) ? data(-inf, -inf) : data(inf, inf);
    else
      change(x, sum[rt].l, 1), change(x, sum[rt].r, 0);
    return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid)
    modify((rt << 1), l, mid, x);
  else
    modify((rt << 1 | 1), mid + 1, r, x);
  sum[rt] = sum[(rt << 1)] + sum[(rt << 1 | 1)];
}
data query(int rt, int l, int r, int x, int y) {
  if (x <= l && r <= y) return sum[rt];
  int mid = (l + r) >> 1;
  if (y <= mid) return query((rt << 1), l, mid, x, y);
  if (x > mid) return query((rt << 1 | 1), mid + 1, r, x, y);
  return query((rt << 1), l, mid, x, y) +
         query((rt << 1 | 1), mid + 1, r, x, y);
}
inline void addedge(int x, int y) {
  to[++tot] = y, nxt[tot] = head[x], head[x] = tot;
}
void dfs1(int x, int ff) {
  siz[x] = 1, fa[x] = ff, dep[x] = dep[ff] + 1;
  int maxson = -1;
  for (int i = head[x]; i; i = nxt[i]) {
    int y = to[i];
    if (y == ff) continue;
    dfs1(y, x), siz[x] += siz[y];
    if (siz[y] > maxson) maxson = siz[y], son[x] = y;
  }
}
void dfs2(int x, int topf) {
  top[x] = topf, id[x] = ++tim, mp[tim] = x;
  if (son[x])
    dfs2(son[x], topf), ed[x] = ed[son[x]];
  else
    ed[x] = id[x];
  for (int i = head[x]; i; i = nxt[i]) {
    int y = to[i];
    if (y == fa[x] || y == son[x]) continue;
    dfs2(y, y);
    lim[y] = query(1, 1, n, id[y], ed[y]).l;
    insert(rt[x], lim[y]);
  }
  modify(1, 1, n, id[x]);
}
int main() {
  srand(19260817);
  n = read(), k = read();
  int op, x, y;
  for (int i = 1; i < n; i++) {
    x = read(), y = read();
    addedge(x, y), addedge(y, x);
  }
  for (int i = 1; i <= n; i++) col[i] = read();
  dfs1(1, 0), dfs2(1, 1);
  m = read();
  while (m--) {
    op = read();
    if (op == 3)
      k = read();
    else if (op == 1)
      x = read(), printf("%d\n", (k >= query(1, 1, n, id[x], ed[x]).l) ? 0 : 1);
    else {
      x = read(), y = read();
      col[x] = y;
      while (x) {
        modify(1, 1, n, id[x]), x = top[x];
        if (x == 1) break;
        erase(rt[fa[x]], lim[x]);
        lim[x] = query(1, 1, n, id[x], ed[x]).l;
        insert(rt[fa[x]], lim[x]);
        x = fa[x];
      }
    }
  }
  return 0;
}