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>
template <typename _Tp>
void read(_Tp &x) {
  char ch(getchar());
  bool f(false);
  while (!isdigit(ch)) f |= ch == 45, ch = getchar();
  x = ch & 15, ch = getchar();
  while (isdigit(ch)) x = x * 10 + (ch & 15), ch = getchar();
  if (f) x = -x;
}
template <typename _Tp, typename... Args>
void read(_Tp &t, Args &...args) {
  read(t);
  read(args...);
}
const int N = 100005, inf = 0x3f3f3f3f;
std::vector<int> e[N];
struct DS {
  std::map<int, int> mp;
  int f, all, cur;
  inline int get(int x) {
    auto it = mp.find(x);
    return it == mp.end() ? 0 : it->second;
  }
  inline void fix() {
    while ((cur - get(f)) * 2 - all >= f + 1) cur -= get(f++);
    while (cur * 2 - all < f) cur += get(--f);
  }
  inline void ins(int x) { cur += x >= f, ++all, ++mp[x], fix(); }
  inline void del(int x) {
    cur -= x >= f, --all;
    if (auto it = mp.find(x); !--it->second) mp.erase(it);
    fix();
  }
} s[N];
int Fa[N], dep[N], siz[N], son[N], top[N], ed[N], dfn[N], rev[N], id, a[N],
    dp[N], n;
struct node {
  int a, b;
} f[N << 2], val[N];
inline node merge(const node &x, const node &y) {
  return x.a < -inf   ? y
         : y.a < -inf ? x
                      : (node){std::max(std::min(y.a, x.b), x.a),
                               std::max(std::min(y.b, x.b), x.a)};
}
int M;
void build(int n) {
  for (M = 1; M <= n + 2; M <<= 1)
    ;
  for (int i = 1; i <= n; ++i) f[i + M] = val[rev[i]];
  for (int i = M - 1; i >= 1; --i) f[i] = merge(f[i << 1], f[i << 1 | 1]);
}
void upd(int x, const node &C) {
  f[x += M] = C;
  for (x >>= 1; x; x >>= 1) f[x] = merge(f[x << 1], f[x << 1 | 1]);
}
node ask(int s, int t) {
  node A = {-inf - 1, -inf - 1}, B = {-inf - 1, -inf - 1};
  for (s += M - 1, t += M + 1; s ^ t ^ 1; s >>= 1, t >>= 1) {
    if (~s & 1) A = merge(A, f[s ^ 1]);
    if (t & 1) B = merge(f[t ^ 1], B);
  }
  return merge(A, B);
}
inline node get(int x) {
  if (~a[x]) return a[x] ? (node){inf, inf} : (node){-inf, -inf};
  int A, B;
  s[x].ins(-inf), A = s[x].f, s[x].del(-inf);
  s[x].ins(inf), B = s[x].f, s[x].del(inf);
  return {A, B};
}
void dfs1(int x, int fa) {
  if (~a[x]) dp[x] = a[x] ? inf : -inf;
  Fa[x] = fa, dep[x] = dep[fa] + 1, siz[x] = 1;
  for (auto v : e[x])
    if (v != fa) {
      dfs1(v, x), siz[x] += siz[v];
      if (siz[v] > siz[son[x]]) son[x] = v;
    }
  for (auto v : e[x])
    if (v != fa && v != son[x]) s[x].ins(dp[v]);
  if (son[x]) s[x].ins(dp[son[x]]), dp[x] = s[x].f, s[x].del(dp[son[x]]);
  val[x] = get(x);
}
void dfs2(int x, int topf) {
  top[x] = topf, dfn[x] = ++id, rev[id] = x, ed[topf] = x;
  if (son[x]) dfs2(son[x], topf);
  for (auto v : e[x])
    if (!top[v]) dfs2(v, v);
}
inline int calc(int x) { return ask(dfn[x], dfn[ed[top[x]]]).a; }
int main() {
  int k;
  read(n, k);
  for (int i = 1, x, y; i < n; ++i)
    read(x, y), e[x].push_back(y), e[y].push_back(x);
  for (int i = 1; i <= n; ++i) read(a[i]);
  dfs1(1, 0), dfs2(1, 1), build(n);
  int q, opt, x, y;
  read(q);
  while (q--) {
    read(opt);
    if (opt == 1)
      read(x), printf("%d\n", k <= calc(x));
    else if (opt == 2) {
      read(x, y), a[x] = y;
      int last = x;
      while (top[x] > 1) {
        x = top[x], s[Fa[x]].del(calc(x)), upd(dfn[last], get(last)),
        s[Fa[x]].ins(calc(x));
        last = Fa[x], x = Fa[x];
      }
      upd(dfn[last], get(last));
    } else
      read(k);
  }
  return 0;
}