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 = 1e5 + 10;
const int M = 3e6 + 10;
int gi() {
  int x = 0, o = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') o = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x * o;
}
namespace treap {
int rt[M], siz[M], ls[M], rs[M], key[M], tt, val[M], st[M], tp;
int newnode(int v) {
  int x;
  if (tp)
    x = st[tp--];
  else
    x = ++tt;
  ls[x] = rs[x] = 0;
  siz[x] = 1;
  key[x] = rand();
  val[x] = v;
  return x;
}
void up(int x) { siz[x] = siz[ls[x]] + siz[rs[x]] + 1; }
int merge(int x, int y) {
  if (!x || !y) return x | y;
  if (key[x] < key[y]) {
    rs[x] = merge(rs[x], y);
    up(x);
    return x;
  } else {
    ls[y] = merge(x, ls[y]);
    up(y);
    return y;
  }
}
void split_val(int x, int v, int &a, int &b) {
  if (!x) {
    a = b = 0;
    return;
  }
  if (val[x] <= v)
    a = x, split_val(rs[x], v, rs[a], b);
  else
    b = x, split_val(ls[x], v, a, ls[b]);
  up(x);
}
void split_rnk(int x, int k, int &a, int &b) {
  if (!x) {
    a = b = 0;
    return;
  }
  if (siz[ls[x]] < k)
    a = x, split_rnk(rs[x], k - siz[ls[x]] - 1, rs[a], b);
  else
    b = x, split_rnk(ls[x], k, a, ls[b]);
  up(x);
}
int getrank(int x, int v) {
  if (!x) return 0;
  if (val[x] <= v) return getrank(rs[x], v) + siz[ls[x]] + 1;
  return getrank(ls[x], v);
}
void insert(int x, int v) {
  int a, b;
  split_val(rt[x], v, a, b);
  rt[x] = merge(a, merge(newnode(v), b));
}
void erase(int x, int v) {
  int a, b, c;
  split_val(rt[x], v, a, b);
  split_rnk(a, siz[a] - 1, a, c);
  st[++tp] = c;
  rt[x] = merge(a, b);
}
int query(int x, int v) { return getrank(rt[x], v); }
}  // namespace treap
struct dat {
  int r, b;
  dat() { r = b = 0; }
  dat(int r, int b) : r(r), b(b) {}
  dat operator+(const dat &A) const {
    return dat(min(b, max(r, A.r)), min(b, max(r, A.b)));
  }
};
int n, k, q, fa[N], son[N], siz[N], dep[N], top[N], id[N], p[N], cnt[N], ls[M],
    rs[M], tt, rt[N], len[N], col[N];
dat tr[M], seq[N], tmp[N];
vector<int> E[N];
bool check(int u, int k, int d) {
  int t = treap::query(u, k);
  return cnt[u] - t - t - d >= k;
}
void update(int u, int &k, int d) {
  while (!check(u, k - 1, d)) --k;
  while (check(u, k, d)) ++k;
}
dat get(int u) {
  if (col[u] == 0) return dat(-1e9, -1e9);
  if (col[u] == 1) return dat(1e9, 1e9);
  update(u, tmp[u].r, 1);
  update(u, tmp[u].b, -1);
  return tmp[u];
}
void dfs(int u, int ff) {
  fa[u] = ff;
  siz[u] = 1;
  dep[u] = dep[ff] + 1;
  for (auto v : E[u])
    if (v ^ ff) {
      dfs(v, u);
      siz[u] += siz[v];
      if (siz[son[u]] < siz[v]) son[u] = v;
    }
}
void dfs2(int u, int tp) {
  top[u] = tp;
  if (son[u]) dfs2(son[u], tp);
  for (auto v : E[u])
    if (v != fa[u] && v != son[u]) ++cnt[u], dfs2(v, v);
}
void build(int &x, int l, int r) {
  x = ++tt;
  if (l == r) {
    tr[x] = seq[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(ls[x], l, mid);
  build(rs[x], mid + 1, r);
  tr[x] = tr[ls[x]] + tr[rs[x]];
}
void modify(int p, dat v, int x, int l, int r) {
  if (l == r) {
    tr[x] = v;
    return;
  }
  int mid = (l + r) >> 1;
  p <= mid ? modify(p, v, ls[x], l, mid) : modify(p, v, rs[x], mid + 1, r);
  tr[x] = tr[ls[x]] + tr[rs[x]];
}
dat query(int L, int R, int x, int l, int r) {
  if (L <= l && r <= R) return tr[x];
  int mid = (l + r) >> 1;
  if (R <= mid) return query(L, R, ls[x], l, mid);
  if (L > mid) return query(L, R, rs[x], mid + 1, r);
  return query(L, R, ls[x], l, mid) + query(L, R, rs[x], mid + 1, r);
}
void dfs3(int u) {
  for (auto v : E[u])
    if (v != fa[u]) dfs3(v);
  if (u == top[u]) {
    int x = u;
    while (x) id[x] = ++len[u], seq[len[u]] = get(x), x = son[x];
    build(rt[u], 1, len[u]);
    p[u] = tr[rt[u]].r;
    if (fa[u]) treap::insert(fa[u], p[u]);
  }
}
void modify_col(int u, int c) {
  if (col[u] == c) return;
  col[u] = c;
  while (u) {
    modify(id[u], get(u), rt[top[u]], 1, len[top[u]]);
    u = top[u];
    if (fa[u]) {
      treap::erase(fa[u], p[u]);
      p[u] = tr[rt[u]].r;
      treap::insert(fa[u], p[u]);
    }
    u = fa[u];
  }
}
int main() {
  srand(20020415);
  cin >> n >> k;
  for (int i = 1, u, v; i < n; i++)
    u = gi(), v = gi(), E[u].push_back(v), E[v].push_back(u);
  for (int i = 1; i <= n; i++) col[i] = gi();
  dfs(1, 0);
  dfs2(1, 1);
  dfs3(1);
  cin >> q;
  while (q--) {
    int op = gi(), u = gi();
    if (op == 1)
      cout << (query(id[u], len[top[u]], rt[top[u]], 1, len[top[u]]).r > k)
           << '\n';
    else if (op == 2)
      modify_col(u, gi());
    else
      k = u;
  }
  return 0;
}