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;
pair<int, int> operator+(pair<int, int> a, pair<int, int> b) {
  if (a.first > b.second || a.second < b.first) return a;
  return {max(a.first, b.first), min(a.second, b.second)};
}
const int N = 100050;
const int inf = 1e9 + 7;
struct Color {
  int deg, cnt, cur, bal;
  vector<int> sz;
  Color() {}
  void init(int d) {
    deg = d;
    cnt = cur = bal = 0;
    sz.clear();
    sz.resize(deg * 2 + 1);
  }
  void upd() {
    while (cur > bal) cur--, bal += 2 * sz[cur + deg];
    while (cur + 1 <= bal - 2 * sz[cur + deg]) bal -= 2 * sz[cur + deg], cur++;
  }
  void Add(int x) {
    cnt++;
    x = min(deg, max(-deg, x));
    sz[x + deg]++;
    if (x >= cur)
      bal++;
    else
      bal--;
    upd();
  }
  void Rem(int x) {
    cnt--;
    x = min(deg, max(-deg, x));
    sz[x + deg]--;
    if (x >= cur)
      bal--;
    else
      bal++;
    upd();
  }
  pair<int, int> Get() {
    if (cnt == deg) return {cur, cur};
    if (cnt == deg - 1) {
      int l = cur, r = cur;
      if (cur == bal) l--;
      if (cur == bal - 2 * sz[cur + deg]) r++;
      return {l, r};
    } else
      return {0, 0};
  }
} C[N];
int fa[N], go[N][2];
pair<int, int> path[N];
int pd(int x) { return go[fa[x]][0] == x ? 0 : go[fa[x]][1] == x ? 1 : -1; }
void pull(int x) { path[x] = (path[go[x][0]] + C[x].Get()) + path[go[x][1]]; }
void rot(int x) {
  int y = fa[x], z = fa[y], p = pd(x), q = pd(y), w = go[x][p ^ 1];
  if (q != -1) go[z][q] = x;
  go[y][p] = w;
  go[x][p ^ 1] = y;
  if (w) fa[w] = y;
  fa[x] = z;
  fa[y] = x;
  pull(y);
  pull(x);
}
void Add(int x, int y) {
  if (y) C[x].Add(path[y].first);
}
void Rem(int x, int y) {
  if (y) C[x].Rem(path[y].first);
}
void splay(int x) {
  while (pd(x) != -1) {
    if (pd(fa[x]) != -1) rot(pd(fa[x]) == pd(x) ? fa[x] : x);
    rot(x);
  }
}
void access(int x) {
  int tmp = x;
  for (int y = 0; x;) {
    splay(x);
    Rem(x, y);
    Add(x, go[x][1]);
    go[x][1] = y;
    pull(x);
    y = x;
    x = fa[x];
  }
  splay(tmp);
}
void link(int x, int y) {
  splay(y);
  access(x);
  go[y][0] = x;
  fa[x] = y;
  pull(y);
}
int n, k, q;
vector<int> E[N];
int par[N], st[N], lf[N];
vector<int> ord;
void DFS(int u, int p) {
  int deg = 0;
  ord.push_back(u);
  for (int v : E[u])
    if (v != p) {
      deg++;
      par[v] = u;
      DFS(v, u);
    }
  C[u].init(deg);
  if (deg == 0) lf[u] = 1;
}
void P(int v) {
  if (lf[v])
    printf("%i\n", st[v]);
  else
    access(v), printf("%i\n", k <= C[v].cur ? 1 : 0);
}
void U(int v, int c) {
  if (st[v] == c) return;
  access(par[v]);
  C[par[v]].Rem(st[v] == 1 ? inf : -inf);
  st[v] = c;
  C[par[v]].Add(st[v] == 1 ? inf : -inf);
  pull(par[v]);
}
int main() {
  path[0] = {-inf, inf};
  scanf("%i %i", &n, &k);
  for (int i = 1, u, v; i < n; i++)
    scanf("%i %i", &u, &v), E[u].push_back(v), E[v].push_back(u);
  for (int i = 1; i <= n; i++) scanf("%i", &st[i]);
  DFS(1, 0);
  for (int i = 2; i <= n; i++)
    if (lf[i]) C[par[i]].Add(st[i] == 1 ? inf : -inf);
  reverse(ord.begin(), ord.end());
  for (int u : ord)
    if (!lf[u]) {
      pull(u);
      if (par[u]) link(par[u], u);
    }
  scanf("%i", &q);
  while (q--) {
    int t, v, c;
    scanf("%i", &t);
    if (t == 1) scanf("%i", &v), P(v);
    if (t == 2) scanf("%i %i", &v, &c), U(v, c);
    if (t == 3) scanf("%i", &k);
  }
  return 0;
}