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;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
struct Func {
  int l, r;
  Func() : l(INT_MIN), r(INT_MAX) {}
  Func(int l, int r) : l(l), r(r) {}
  int val() {
    assert(l == r);
    return l;
  }
};
void merge(Func &a, const Func &b) {
  a = Func(max(a.l, min(a.r, b.l)), max(a.l, min(a.r, b.r)));
}
struct ColorCalculator {
  int id, deg;
  vector<int> chcnt;
  int chsum;
  int cur, bal;
  void init(int _id, int _deg) {
    id = _id, deg = _deg;
    chcnt = vector<int>(2 * deg + 1, 0);
    chsum = 0;
    cur = 0, bal = 0;
  }
  void addchild(int k) {
    ++chsum;
    k = max(-deg, min(+deg, k));
    ++chcnt[deg + k];
    if (k >= cur)
      ++bal;
    else
      --bal;
    upd();
  }
  void remchild(int k) {
    --chsum;
    k = max(-deg, min(+deg, k));
    --chcnt[deg + k];
    if (k >= cur)
      --bal;
    else
      ++bal;
    upd();
  }
  void upd() {
    while (bal < cur) --cur, bal += 2 * chcnt[deg + cur];
    while (bal - 2 * chcnt[deg + cur] >= cur + 1)
      bal -= 2 * chcnt[deg + cur], ++cur;
  }
  Func func() {
    if (chsum == deg) return Func(cur, cur);
    if (chsum == deg - 1)
      return Func(cur - (bal == cur ? 1 : 0),
                  cur + (bal - 2 * chcnt[deg + cur] == cur ? 1 : 0));
    return Func(0, 0);
  }
};
struct LinkCutNode {
  int par, ch[2];
  ColorCalculator midcol;
  Func pathfunc;
};
struct LinkCutTree {
  void updatepath(LinkCutNode &x, LinkCutNode *l, LinkCutNode *r) {
    x.pathfunc = Func();
    if (l != nullptr) merge(x.pathfunc, l->pathfunc);
    merge(x.pathfunc, x.midcol.func());
    if (r != nullptr) merge(x.pathfunc, r->pathfunc);
  }
  void removemiddle(LinkCutNode &x, LinkCutNode *y) {
    x.midcol.remchild(y->pathfunc.val());
  }
  void addmiddle(LinkCutNode &x, LinkCutNode *y) {
    x.midcol.addchild(y->pathfunc.val());
  }
  vector<LinkCutNode> nodes;
  void init(int n) {
    nodes = vector<LinkCutNode>(n);
    for (int x = (0); x < (((int)(nodes).size())); ++x) {
      nodes[x].par = nodes[x].ch[0] = nodes[x].ch[1] = -1;
    }
  }
  bool isroot(int x) {
    return nodes[x].par == -1 ||
           nodes[nodes[x].par].ch[0] != x && nodes[nodes[x].par].ch[1] != x;
  }
  int side(int x, int y) {
    return nodes[y].ch[0] == x ? 0 : nodes[y].ch[1] == x ? 1 : -1;
  }
  void updatepath(int x) {
    updatepath(nodes[x],
               nodes[x].ch[0] == -1 ? nullptr : &nodes[nodes[x].ch[0]],
               nodes[x].ch[1] == -1 ? nullptr : &nodes[nodes[x].ch[1]]);
  }
  void removemiddle(int x, int y) {
    if (y != -1) removemiddle(nodes[x], &nodes[y]);
  }
  void addmiddle(int x, int y) {
    if (y != -1) addmiddle(nodes[x], &nodes[y]);
  }
  void rotate(int x) {
    assert(!isroot(x));
    int y = nodes[x].par, z = nodes[y].par, k = side(x, y);
    assert(k == 0 || k == 1);
    assert(y != -1);
    nodes[x].par = z;
    if (!isroot(y)) nodes[z].ch[side(y, z)] = x;
    nodes[y].ch[k] = nodes[x].ch[1 - k];
    if (nodes[y].ch[k] != -1) nodes[nodes[y].ch[k]].par = y;
    nodes[x].ch[1 - k] = y, nodes[y].par = x;
    updatepath(y), updatepath(x);
  }
  void splay(int x) {
    while (!isroot(x)) {
      int y = nodes[x].par, z = nodes[y].par;
      if (!isroot(y)) rotate(side(x, y) != side(y, z) ? x : y);
      rotate(x);
    }
  }
  void access(int x) {
    for (int y = -1; x != -1; y = x, x = nodes[x].par) {
      splay(x);
      removemiddle(x, y);
      addmiddle(x, nodes[x].ch[1]);
      nodes[x].ch[1] = y;
      updatepath(x);
    }
  }
  void link(int x, int y) {
    splay(x);
    assert(nodes[x].par == -1 && nodes[x].ch[0] == -1);
    access(y);
    splay(y);
    assert(nodes[y].par == -1 && nodes[y].ch[1] == -1);
    nodes[x].ch[0] = y, nodes[y].par = x;
    updatepath(x);
  }
  void cut(int x) {
    access(x);
    splay(x);
    assert(nodes[x].par == -1 && nodes[x].ch[0] != -1);
    int y = nodes[x].ch[0];
    nodes[y].par = -1;
    nodes[x].ch[0] = -1;
    updatepath(x);
  }
};
const int MAXN = 100000;
const int MAXQ = 100000;
int n, skglob;
vector<int> adj[MAXN];
int scol[MAXN];
int nq;
int qkind[MAXQ], qidx[MAXQ], qval[MAXQ], qans[MAXQ];
int par[MAXN], deg[MAXN];
LinkCutTree tree;
int kglob;
int col[MAXN];
bool isleaf[MAXN];
int pre[MAXN], npre;
void dfsinit(int at) {
  pre[npre++] = at;
  deg[at] = 0;
  isleaf[at] = scol[at] != -1;
  for (int i = (0); i < (((int)(adj[at]).size())); ++i) {
    int to = adj[at][i];
    if (to == par[at]) continue;
    ++deg[at];
    par[to] = at;
    dfsinit(to);
  }
}
bool query(int x) {
  if (isleaf[x]) return col[x] == 1;
  tree.access(x);
  tree.splay(x);
  return tree.nodes[x].midcol.func().val() >= kglob;
}
void update(int x, int c) {
  if (col[x] == c) return;
  assert(isleaf[x]);
  int y = par[x];
  if (y != -1) tree.access(y), tree.splay(y);
  if (y != -1) tree.nodes[y].midcol.remchild(col[x] == 1 ? INT_MAX : INT_MIN);
  col[x] = c;
  if (y != -1) tree.nodes[y].midcol.addchild(col[x] == 1 ? INT_MAX : INT_MIN);
  if (y != -1) tree.updatepath(y);
}
void solve() {
  par[0] = -1;
  npre = 0;
  dfsinit(0);
  tree.init(n);
  for (int i = (0); i < (n); ++i)
    if (!isleaf[i]) tree.nodes[i].midcol.init(i, deg[i]);
  for (int i = (0); i < (n); ++i)
    if (isleaf[i] && par[i] != -1)
      tree.nodes[par[i]].midcol.addchild(scol[i] == 1 ? INT_MAX : INT_MIN);
  for (int i = (0); i < (n); ++i) {
    int at = pre[n - i - 1];
    if (isleaf[at]) continue;
    tree.updatepath(at);
    if (par[at] == -1) continue;
    tree.link(at, par[at]);
  }
  kglob = skglob;
  for (int i = (0); i < (n); ++i) col[i] = scol[i];
  for (int i = (0); i < (nq); ++i) {
    if (qkind[i] == 1) qans[i] = query(qidx[i]) ? 1 : 0;
    if (qkind[i] == 2) update(qidx[i], qval[i]);
    if (qkind[i] == 3) kglob = qval[i];
  }
}
void run() {
  scanf("%d%d", &n, &skglob);
  for (int i = (0); i < (n - 1); ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a, --b;
    adj[a].push_back(b), adj[b].push_back(a);
  }
  for (int i = (0); i < (n); ++i) scanf("%d", &scol[i]);
  scanf("%d", &nq);
  for (int i = (0); i < (nq); ++i) {
    scanf("%d", &qkind[i]);
    if (qkind[i] == 1) scanf("%d", &qidx[i]), --qidx[i];
    if (qkind[i] == 2) scanf("%d%d", &qidx[i], &qval[i]), --qidx[i];
    if (qkind[i] == 3) scanf("%d", &qval[i]);
  }
  solve();
  for (int i = (0); i < (nq); ++i)
    if (qkind[i] == 1) printf("%d\n", qans[i]);
}
int main() {
  run();
  return 0;
}