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 char nc() {
  return getchar();
  static char buf[100000], *l = buf, *r = buf;
  return l == r && (r = (l = buf) + fread(buf, 1, 100000, stdin), l == r)
             ? EOF
             : *l++;
}
template <class T>
void read(T &x) {
  x = 0;
  int f = 1, ch = nc();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = nc();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 - '0' + ch;
    ch = nc();
  }
  x *= f;
}
const int inf = 1e9;
const int maxn = 1e5 + 10;
int n, k, q;
int s[maxn];
int dfc;
int en[maxn];
int anc[maxn];
int dep[maxn];
int dfn[maxn];
int rec[maxn];
int rnk[maxn];
int siz[maxn];
int son[maxn];
int top[maxn];
int head[maxn];
int root[maxn];
struct data {
  int l, r;
  data(int l = 0, int r = 0) : l(l), r(r) {}
};
data red = {inf, inf};
data blue = {-inf, -inf};
data merge(data L, data R) {
  data re;
  re.l = min(max(R.l, L.l), L.r);
  re.r = min(max(R.r, L.l), L.r);
  return re;
}
struct edge {
  int to, nex;
  edge(int to = 0, int nex = 0) : to(to), nex(nex) {}
};
vector<edge> G;
inline void addedge(int u, int v) {
  G.push_back(edge(v, head[u])), head[u] = G.size() - 1;
  G.push_back(edge(u, head[v])), head[v] = G.size() - 1;
}
namespace trp {
int all;
int cnt[maxn];
int key[maxn];
int rnk[maxn];
int siz[maxn];
int temp[maxn];
int ch[maxn][2];
inline void pushup(int u) { siz[u] = siz[ch[u][0]] + cnt[u] + siz[ch[u][1]]; }
inline void rotate(int &x, int d) {
  int y = ch[x][d ^ 1];
  ch[x][d ^ 1] = ch[y][d];
  ch[y][d] = x;
  pushup(x);
  pushup(y);
  x = y;
}
inline void newnode(int &u, int k) {
  u = temp[0] ? temp[temp[0]--] : ++all;
  cnt[u] = 1;
  key[u] = k;
  rnk[u] = rand();
  siz[u] = 1;
  ch[u][0] = ch[u][1] = 0;
}
int myrank(int u, int k) {
  if (u == 0) return 0;
  if (k < key[u])
    return myrank(ch[u][0], k);
  else if (k == key[u])
    return siz[ch[u][0]] + cnt[u];
  else {
    return siz[ch[u][0]] + cnt[u] + myrank(ch[u][1], k);
  }
}
void insert(int &u, int k) {
  if (u == 0) {
    newnode(u, k);
    return;
  }
  if (k == key[u]) {
    ++cnt[u];
  } else if (k < key[u]) {
    insert(ch[u][0], k);
    if (rnk[ch[u][0]] < rnk[u]) rotate(u, 1);
  } else {
    insert(ch[u][1], k);
    if (rnk[ch[u][1]] < rnk[u]) rotate(u, 0);
  }
  pushup(u);
}
void remove(int &u, int k) {
  if (k == key[u]) {
    if (cnt[u] > 1)
      --cnt[u];
    else {
      if (!ch[u][0] || !ch[u][1]) {
        temp[++temp[0]] = u;
        u = ch[u][0] + ch[u][1];
      } else {
        rotate(u, rnk[ch[u][0]] < rnk[ch[u][1]]);
        remove(u, k);
      }
    }
  } else if (k < key[u]) {
    remove(ch[u][0], k);
  } else {
    remove(ch[u][1], k);
  }
  pushup(u);
}
}  // namespace trp
bool judge(int u, int k, int d) {
  int b = trp ::myrank(root[u], k);
  int r = trp ::siz[root[u]] - b;
  return k >= r - b + d;
}
void update(int u, int &k, int d) {
  while (!judge(u, k, d)) ++k;
  while (judge(u, k - 1, d)) --k;
}
void update(data &x, int u) {
  if (s[u] == 0) {
    x = red;
  } else if (s[u] == 1) {
    x = blue;
  } else {
    update(u, x.l, -1);
    update(u, x.r, 1);
  }
}
namespace seg {
data f[maxn << 2];
inline void pushup(int u) { f[u] = merge(f[u << 1], f[u << 1 | 1]); }
data query(int u, int l, int r, int ql, int qr) {
  if (l == ql && r == qr) {
    return f[u];
  }
  int mid = (l + r) >> 1;
  if (qr <= mid)
    return query(u << 1, l, mid, ql, qr);
  else if (ql > mid)
    return query(u << 1 | 1, mid + 1, r, ql, qr);
  else {
    data L = query(u << 1, l, mid, ql, mid);
    data R = query(u << 1 | 1, mid + 1, r, mid + 1, qr);
    return merge(L, R);
  }
}
void build(int u, int l, int r) {
  if (l == r) {
    int x = rnk[l];
    update(f[u], x);
    if (x == top[x] && anc[x] != 0) {
      trp ::insert(root[anc[x]], rec[x] = query(1, 1, n, l, dfn[en[x]]).l);
    }
    return;
  }
  int mid = (l + r) >> 1;
  build(u << 1 | 1, mid + 1, r);
  build(u << 1, l, mid);
  pushup(u);
}
void update(int u, int l, int r, int qp) {
  if (l == r) {
    update(f[u], rnk[l]);
    return;
  }
  int mid = (l + r) >> 1;
  if (qp <= mid)
    update(u << 1, l, mid, qp);
  else
    update(u << 1 | 1, mid + 1, r, qp);
  pushup(u);
}
}  // namespace seg
void dfs1(int u) {
  siz[u] = 1;
  for (int i = head[u]; ~i; i = G[i].nex) {
    int v = G[i].to;
    if (v == anc[u]) continue;
    anc[v] = u;
    dep[v] = dep[u] + 1;
    dfs1(v);
    siz[u] += siz[v];
    if (siz[son[u]] <= siz[v]) son[u] = v;
  }
}
void dfs2(int u, int chain) {
  top[u] = chain, en[chain] = u;
  dfn[u] = ++dfc;
  rnk[dfc] = u;
  if (son[u]) {
    dfs2(son[u], chain);
  }
  for (int i = head[u]; ~i; i = G[i].nex) {
    int v = G[i].to;
    if (v == anc[u] || v == son[u]) continue;
    dfs2(v, v);
  }
}
void modify(int u, int c) {
  s[u] = c;
  while (u) {
    seg ::update(1, 1, n, dfn[u]);
    u = top[u];
    trp ::remove(root[anc[u]], rec[u]);
    trp ::insert(root[anc[u]],
                 rec[u] = seg ::query(1, 1, n, dfn[u], dfn[en[u]]).l);
    u = anc[u];
  }
}
int main() {
  srand((unsigned long long)(new char));
  read(n), read(k);
  memset(head, -1, sizeof(head));
  for (int i = 1; i < n; ++i) {
    int u, v;
    read(u), read(v);
    addedge(u, v);
  }
  for (int i = 1; i <= n; ++i) {
    read(s[i]);
  }
  dfs1(1);
  dfs2(1, 1);
  seg ::build(1, 1, n);
  read(q);
  for (int i = 1; i <= q; ++i) {
    int op;
    read(op);
    if (op == 1) {
      int v;
      read(v);
      printf("%d\n", seg ::query(1, 1, n, dfn[v], dfn[en[top[v]]]).l <= -k);
    } else if (op == 2) {
      int v, c;
      read(v), read(c);
      modify(v, c);
    } else if (op == 3) {
      int h;
      read(h);
      k = h;
    }
  }
  return 0;
}