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 MAXN = 2e5 + 5;
const int INF = 1e9 + 7;
template <typename T>
void chkmax(T &x, T y) {
  x = max(x, y);
}
template <typename T>
void chkmin(T &x, T y) {
  x = min(x, y);
}
template <typename T>
void read(T &x) {
  x = 0;
  int f = 1;
  char c = getchar();
  for (; !isdigit(c); c = getchar())
    if (c == '-') f = -f;
  for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
  x *= f;
}
template <typename T>
void write(T x) {
  if (x < 0) x = -x, putchar('-');
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
void writeln(T x) {
  write(x);
  puts("");
}
struct info {
  int r, b;
};
info operator+(info a, info b) {
  info ans;
  ans.r = min(max(a.r, b.b), b.r);
  ans.b = min(max(a.b, b.b), b.r);
  return ans;
}
int n, q, h, c[MAXN];
vector<int> a[MAXN];
int father[MAXN], size[MAXN], son[MAXN];
int timer, dfn[MAXN], rit[MAXN], home[MAXN];
int down[MAXN], up[MAXN];
info red() { return (info){INF, INF}; }
info blue() { return (info){-INF, -INF}; }
struct SegmentTree {
  struct Node {
    int lc, rc;
    info sum;
  } a[MAXN * 2];
  int root, size, n;
  void build(int &root, int l, int r) {
    root = ++size;
    if (l == r) return;
    int mid = (l + r) / 2;
    build(a[root].lc, l, mid);
    build(a[root].rc, mid + 1, r);
  }
  void init(int x) {
    n = x;
    root = size = 0;
    build(root, 1, n);
  }
  void update(int root) { a[root].sum = a[a[root].rc].sum + a[a[root].lc].sum; }
  void modify(int root, int l, int r, int pos, info val) {
    if (l == r) {
      a[root].sum = val;
      return;
    }
    int mid = (l + r) / 2;
    if (mid >= pos)
      modify(a[root].lc, l, mid, pos, val);
    else
      modify(a[root].rc, mid + 1, r, pos, val);
    update(root);
  }
  void modify(int pos, info val) { modify(root, 1, n, pos, val); }
  info query(int root, int l, int r, int ql, int qr) {
    if (l == ql && r == qr) return a[root].sum;
    int mid = (l + r) / 2;
    if (mid >= qr)
      return query(a[root].lc, l, mid, ql, qr);
    else if (mid + 1 <= ql)
      return query(a[root].rc, mid + 1, r, ql, qr);
    else
      return query(a[root].rc, mid + 1, r, mid + 1, qr) +
             query(a[root].lc, l, mid, ql, mid);
  }
  int query(int l, int r) {
    info ans = query(root, 1, n, l, r);
    assert(ans.r == ans.b);
    return ans.r;
  }
} ST;
void dfs(int pos, int fa) {
  size[pos] = 1;
  father[pos] = fa;
  for (auto x : a[pos])
    if (x != fa) {
      dfs(x, pos), size[pos] += size[x];
      if (size[x] > size[son[pos]]) son[pos] = x;
    }
}
map<int, int> light[MAXN];
info now[MAXN];
int value[MAXN];
int d[MAXN], cntr[MAXN], cntb[MAXN];
void efs(int pos, int fa, int from) {
  up[pos] = from;
  dfn[pos] = ++timer;
  home[timer] = pos;
  if (son[pos]) {
    d[pos]++;
    efs(son[pos], pos, from);
    down[pos] = down[son[pos]];
  } else
    down[pos] = pos;
  for (auto x : a[pos])
    if (x != fa && x != son[pos]) {
      efs(x, pos, x), d[pos]++;
    }
  rit[pos] = timer;
}
void updatenow(int pos) {
  while (d[pos] - 2 * (cntb[pos] + 1) > now[pos].b) {
    now[pos].b++;
    cntb[pos] += light[pos][now[pos].b];
  }
  while (d[pos] - 2 * (cntb[pos] + 1 - light[pos][now[pos].b]) <=
         now[pos].b - 1) {
    cntb[pos] -= light[pos][now[pos].b];
    now[pos].b--;
  }
  while (d[pos] - 2 * (cntr[pos]) > now[pos].r) {
    now[pos].r++;
    cntr[pos] += light[pos][now[pos].r];
  }
  while (d[pos] - 2 * (cntr[pos] - light[pos][now[pos].r]) <= now[pos].r - 1) {
    cntr[pos] -= light[pos][now[pos].r];
    now[pos].r--;
  }
}
void init(int pos, int fa) {
  if (son[pos])
    init(son[pos], pos);
  else {
    if (c[pos] == 0)
      now[pos] = red();
    else
      now[pos] = blue();
    ST.modify(dfn[pos], now[pos]);
    return;
  }
  for (auto x : a[pos])
    if (x != fa && x != son[pos]) {
      init(x, pos);
      int res = ST.query(dfn[x], dfn[down[x]]);
      light[pos][res]++;
      if (res <= now[pos].b) cntb[pos]++;
      if (res <= now[pos].r) cntr[pos]++;
    }
  updatenow(pos);
  ST.modify(dfn[pos], now[pos]);
}
void modify(int pos) {
  pos = up[pos];
  while (pos != 1) {
    int f = father[pos];
    light[f][value[pos]]--;
    if (value[pos] <= now[f].b) cntb[f]--;
    if (value[pos] <= now[f].r) cntr[f]--;
    value[pos] = ST.query(dfn[pos], dfn[down[pos]]);
    light[f][value[pos]]++;
    if (value[pos] <= now[f].b) cntb[f]++;
    if (value[pos] <= now[f].r) cntr[f]++;
    updatenow(f);
    ST.modify(dfn[f], now[f]);
    pos = up[f];
  }
}
int main() {
  read(n), read(h);
  for (int i = 1; i <= n - 1; i++) {
    int x, y;
    read(x), read(y);
    a[x].push_back(y);
    a[y].push_back(x);
  }
  for (int i = 1; i <= n; i++) read(c[i]);
  dfs(1, 0);
  efs(1, 0, 1);
  ST.init(n);
  init(1, 0);
  for (int i = 1; i <= n; i++)
    if (up[i] == i) {
      value[i] = ST.query(dfn[i], dfn[down[i]]);
    }
  read(q);
  while (q--) {
    int opt, x;
    read(opt);
    if (opt == 1) {
      read(x);
      int res = ST.query(dfn[x], dfn[down[x]]);
      printf("%d\n", res <= -h);
    }
    if (opt == 2) {
      read(x), read(c[x]);
      if (c[x] == 1)
        now[x] = blue();
      else
        now[x] = red();
      ST.modify(dfn[x], now[x]);
      modify(x);
    }
    if (opt == 3) {
      read(h);
    }
  }
  return 0;
}