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;
int n, k;
struct EDGE {
  int to;
  EDGE *las;
} e[100010 * 2];
int ne;
EDGE *last[100010];
void link(int u, int v) {
  e[ne] = {v, last[u]};
  last[u] = e + ne++;
}
int a[100010], d[100010], t[100010];
int fa[100010], siz[100010], hs[100010], top[100010], dfn[100010], nowdfn,
    re[100010], tail[100010];
void dfs1(int x) {
  siz[x] = 1;
  for (EDGE *ei = last[x]; ei; ei = ei->las)
    if (ei->to != fa[x]) {
      fa[ei->to] = x, dfs1(ei->to);
      siz[x] += siz[ei->to];
      if (siz[ei->to] > siz[hs[x]]) hs[x] = ei->to;
    }
}
void dfs2(int x, int t) {
  top[x] = t, tail[t] = x;
  dfn[x] = ++nowdfn, re[nowdfn] = x;
  if (hs[x]) dfs2(hs[x], t);
  for (EDGE *ei = last[x]; ei; ei = ei->las)
    if (ei->to != fa[x] && ei->to != hs[x]) dfs2(ei->to, ei->to);
}
struct Info {
  int a, b;
} s[100010 * 4], f[100010];
Info operator*(Info x, Info y) {
  return (Info){min(max(y.a, x.a), x.b), min(max(y.b, x.a), x.b)};
}
void build(int k, int l, int r) {
  if (l == r) {
    s[k] = f[re[l]];
    return;
  }
  int mid = l + r >> 1;
  build(k << 1, l, mid), build(k << 1 | 1, mid + 1, r);
  s[k] = s[k << 1] * s[k << 1 | 1];
}
Info res;
void getpro(int k, int l, int r, int st, int en) {
  if (st <= l && r <= en) {
    res = res * s[k];
    return;
  }
  int mid = l + r >> 1;
  if (st <= mid) getpro(k << 1, l, mid, st, en);
  if (mid < en) getpro(k << 1 | 1, mid + 1, r, st, en);
}
void modify(int k, int l, int r, int x, Info c) {
  if (l == r) {
    s[k] = c;
    return;
  }
  int mid = l + r >> 1;
  x <= mid ? modify(k << 1, l, mid, x, c)
           : modify(k << 1 | 1, mid + 1, r, x, c);
  s[k] = s[k << 1] * s[k << 1 | 1];
}
struct Node *null;
struct Node {
  Node *fa, *c[2];
  int v, siz;
  void upd() { siz = c[0]->siz + c[1]->siz + 1; }
  bool getson() { return fa->c[0] != this; }
  void rotate() {
    Node *y = fa, *z = y->fa;
    if (z != null) z->c[y->getson()] = this;
    bool k = getson();
    fa = z;
    y->c[k] = c[!k], c[!k]->fa = y;
    c[!k] = y, y->fa = this;
    siz = y->siz, y->upd();
  }
  void splay(Node *t = null) {
    for (; fa != t; rotate())
      if (fa->fa != t) getson() != fa->getson() ? rotate() : fa->rotate();
  }
} * rt[100010];
Node *getBST(int q[], int l, int r) {
  if (l > r) return null;
  int mid = l + r >> 1;
  Node *nw = new Node;
  *nw = {null, getBST(q, l, mid - 1), getBST(q, mid + 1, r), q[mid], 1};
  nw->c[0]->fa = nw->c[1]->fa = nw, nw->upd();
  return nw;
}
Node *find(Node *t, int v) {
  if (t->v == v) return t;
  return v < t->v ? find(t->c[0], v) : find(t->c[1], v);
}
void erase(Node *&rt, int v) {
  Node *t = find(rt, v);
  t->splay();
  if (t->c[0] == null)
    rt = t->c[1];
  else {
    Node *pre = t->c[0];
    for (; pre->c[1] != null; pre = pre->c[1])
      ;
    pre->splay(t);
    pre->c[1] = t->c[1], t->c[1]->fa = pre;
    pre->upd();
    rt = pre;
  }
  rt->fa = null;
  delete t;
}
void insert(Node *&rt, int v) {
  Node *t = rt, *nw = new Node;
  while (1) {
    t->siz++;
    if (v < t->v)
      if (t->c[0] == null) {
        t->c[0] = nw;
        *nw = {t, null, null, v, 1};
        break;
      } else
        t = t->c[0];
    else if (t->c[1] == null) {
      t->c[1] = nw;
      *nw = {t, null, null, v, 1};
      break;
    } else
      t = t->c[1];
  }
  nw->splay(), rt = nw;
}
Node *search(Node *t, int dx) {
  if (t == null) return null;
  if (t->v + 2 * (t->c[0]->siz + 1) <= dx)
    return search(t->c[1], dx - 2 * (t->c[0]->siz + 1));
  Node *res = search(t->c[0], dx);
  return res != null ? res : t;
}
int cntpred(Node *t, int v) {
  if (t == null) return 0;
  if (v <= t->v) return cntpred(t->c[0], v);
  return cntpred(t->c[1], v) + 1 + t->c[0]->siz;
}
int calc(Node *t, int dx) {
  Node *p = search(t, dx);
  if (p == null) return dx - 2 * t->siz + 1;
  return min(dx - 2 * cntpred(t, p->v) + 1, p->v);
}
Info getf(int x) {
  int a, b;
  Node *t = rt[x];
  for (; t->c[1] != null; t = t->c[1])
    ;
  t->splay(), rt[x] = t;
  a = calc(t->c[0], d[x]);
  for (; t->c[0] != null; t = t->c[0])
    ;
  t->splay(), rt[x] = t;
  b = calc(t->c[1], d[x]);
  return {a, b};
}
int calc_init(int dx, int q[], int cnt) {
  int k = -1000000000;
  for (int i = 1, j = 0; i <= cnt; ++i)
    if (i == cnt || q[i] != q[i + 1]) {
      if (dx - q[i] < 2 * i) return min(dx - 2 * j + 1, q[i]);
      k = q[i], j = i;
    }
  return dx - 2 * cnt + 1;
}
void dp(int x) {
  d[x] = 0;
  for (EDGE *ei = last[x]; ei; ei = ei->las)
    if (ei->to != fa[x]) dp(ei->to), d[x]++;
  if (d[x] == 0) {
    t[x] = (a[x] == 0 ? -1000000000 : 1000000000);
    return;
  }
  static int q[100010];
  int cnt = 0;
  for (EDGE *ei = last[x]; ei; ei = ei->las)
    if (ei->to != fa[x]) q[++cnt] = t[ei->to];
  sort(q + 1, q + cnt + 1);
  t[x] = calc_init(d[x], q, cnt);
  for (int i = 1; i <= cnt; ++i)
    if (q[i] == t[hs[x]]) {
      for (; i < cnt; ++i) q[i] = q[i + 1];
      cnt--;
      break;
    }
  q[0] = -1000000000, q[cnt + 1] = 1000000000;
  rt[x] = getBST(q, 0, cnt + 1);
  f[x] = getf(x);
}
int query(int x) {
  int y = tail[top[x]];
  res = {-1000000000, 1000000000};
  if (x != y) getpro(1, 1, n, dfn[x], dfn[y] - 1);
  return a[y] == 0 ? res.a : res.b;
}
void change(int x, int c) {
  if (a[x] == c) return;
  a[x] = c;
  for (x = top[x]; fa[x]; x = top[fa[x]]) {
    int y = fa[x];
    erase(rt[y], t[x]);
    t[x] = query(x);
    insert(rt[y], t[x]);
    f[y] = getf(y);
    modify(1, 1, n, dfn[y], f[y]);
  }
}
int main() {
  null = new Node;
  *null = {null, null, null, -1000000000, 0};
  scanf("%d%d", &n, &k);
  for (int i = 1; i < n; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    link(u, v), link(v, u);
  }
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  dfs1(1), dfs2(1, 1);
  dp(1);
  build(1, 1, n);
  int Q;
  scanf("%d", &Q);
  while (Q--) {
    int op;
    scanf("%d", &op);
    if (op == 1) {
      int x;
      scanf("%d", &x);
      printf("%d\n", k < query(x));
    } else if (op == 2) {
      int x, c;
      scanf("%d%d", &x, &c);
      change(x, c);
    } else
      scanf("%d", &k);
  }
  return 0;
}