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 = 100005;
int n, K, m, i, j, o, u, v, s[N];
vector<int> e[N], a[N];
int top[N], len[N], bot[N], dep[N], deg[N], sz[N], qsz[N], ma[N], dad[N], rt[N],
    trs[27][27], mp[27][3];
int st[N], dfn[N], xb, id[N];
bool isl[N];
void dfs(int u, int fa) {
  sz[u] = 1;
  dad[u] = fa;
  dfn[++xb] = u;
  dep[u] = dep[fa] + 1;
  for (int v : e[u])
    if (v != fa)
      dfs(v, u), sz[v] > sz[ma[u]] ? ma[u] = v : 0, ++deg[u], sz[u] += sz[v];
  if (!isl[u]) a[u].resize(deg[u] * 2 + 3);
  qsz[u] = sz[u] - sz[ma[u]];
}
int pp[N], ps[N], f[N];
inline void fix(int x) {
  if (!x) return;
  for (; ps[x] - a[x][pp[x] + deg[x] + 1] * 2 >= pp[x] + 1;
       ps[x] -= a[x][pp[x]++ + deg[x] + 1] * 2)
    ;
  for (; ps[x] < pp[x]; ps[x] += a[x][--pp[x] + deg[x] + 1] * 2)
    ;
}
inline void add(int x, int w, int v) {
  if (x)
    w = min((int)a[x].size() - 1, max(w + deg[x] + 1, 0)), a[x][w] += v,
    ps[x] += w - deg[x] - 1 >= pp[x] ? v : -v;
}
int calc(int x, int w) {
  if (w >= pp[x])
    return (ps[x] - a[x][pp[x] + deg[x] + 1] * 2 + (w > pp[x] ? 1 : -1) >=
            pp[x] + 1) +
           1;
  else
    return ps[x] - 1 >= pp[x];
}
struct node {
  int l, r, md, s;
} t[N * 2];
int tcnt;
inline void maintain(int i) { t[i].s = trs[t[t[i].l].s][t[t[i].r].s]; }
void reget(int i) {
  int u = t[i].l, v = isl[ma[u]] ? f[ma[u]] : pp[ma[u]];
  t[i].s = calc(u, v - 1) + calc(u, v) * 3 + calc(u, v + 1) * 9;
}
void mdy(int i, int l, int r, int k) {
  if (l == r) return reget(i);
  if (k <= t[i].md)
    mdy(t[i].l, l, t[i].md, k);
  else
    mdy(t[i].r, t[i].md + 1, r, k);
  maintain(i);
}
int ask(int i, int l, int r, int k) {
  if (k <= l) return t[i].s;
  return k <= t[i].md ? trs[ask(t[i].l, l, t[i].md, k)][t[t[i].r].s]
                      : ask(t[i].r, t[i].md + 1, r, k);
}
void build(int& x, int l, int r) {
  x = ++tcnt;
  if (l == r) return fix(t[x].l = st[l]), reget(x);
  int s = 0, ss = 0, z, mn = N * 10, i;
  for (i = l; i <= r; ++i) s += qsz[st[i]] + qsz[st[i + 1]];
  for (i = l; i < r; ++i)
    if (ss += qsz[st[i]] + qsz[st[i + 1]], z = max(ss, s - ss), z < mn)
      mn = z, t[x].md = i;
  build(t[x].r, t[x].md + 1, r);
  build(t[x].l, l, t[x].md);
  maintain(x);
}
inline int ask(int v) {
  return isl[v] ? s[v]
                : K <= pp[v] +
                           mp[ask(rt[top[v]], 1, len[top[v]],
                                  dep[v] - dep[top[v]] + 1)][1] -
                           1;
}
inline void mdy(int v) {
  do {
    u = top[v];
    i = f[u];
    add(dad[u], f[u], -1);
    if (!isl[v])
      mdy(rt[u], 1, len[u], dep[v] - dep[u] + 1);
    else
      f[v] = s[v] ? N : -N;
    if (u != v) mdy(rt[u], 1, len[u], dep[v] - dep[u]);
    if (!isl[u]) f[u] = pp[u] + mp[t[rt[u]].s][1] - 1;
    add(dad[u], f[u], 1);
    fix(dad[u]);
  } while (v = dad[u], v && f[u] != i);
}
int main() {
  for (i = 0; i < 27; ++i)
    mp[i][0] = i % 3, mp[i][1] = i / 3 % 3, mp[i][2] = i / 9;
  for (i = 0; i < 27; ++i)
    for (j = 0; j < 27; ++j)
      trs[i][j] = mp[i][mp[j][0]] + mp[i][mp[j][1]] * 3 + mp[i][mp[j][2]] * 9;
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> K;
  for (i = 1; i < n; ++i) cin >> u >> v, e[u].push_back(v), e[v].push_back(u);
  for (i = 1; i <= n; ++i)
    cin >> s[i], f[i] = s[i] == -1 ? 0 : (isl[i] = 1, s[i] ? N : -N);
  top[1] = 1;
  dfs(1, 0);
  for (i = n; i; --i)
    if (u = dfn[i], ma[dad[u]] != u) {
      for (xb = 0, v = u; top[st[++xb] = u] = v, ma[u]; u = ma[u])
        ;
      bot[v] = u;
      if (xb > 1)
        build(rt[v], 1, len[v] = xb - 1), f[v] = pp[v] + mp[t[rt[v]].s][1] - 1;
      add(dad[v], f[v], 1);
    }
  for (cin >> m; m--;) {
    cin >> o >> v;
    if (o == 1) cout << ask(v) << '\n';
    if (o == 2) cin >> s[v], mdy(v);
    if (o == 3) K = v;
  }
  return 0;
}