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 = 200500, K = 450;
vector<int> g[N], G[N], gg[N];
int n, k, q, ms[N], dp0[N], dp1[N], mxk[N], pr[N], type[N], a[N], b[N], c[N];
bool leaf[N];
void dfs(int v, int p) {
  pr[v] = p;
  for (auto to : g[v])
    if (to != p) dfs(to, v);
}
void dfsm(int v) {
  int cnt = (ms[v] != -1);
  for (auto to : g[v])
    if (to != pr[v]) {
      dfsm(to);
      if (ms[to] == -1) continue;
      ms[v] = ms[to];
      cnt++;
    }
  if (cnt > 1) ms[v] = v;
  if (ms[v] == v) {
    for (auto to : g[v])
      if (to != pr[v]) {
        if (ms[to] != -1)
          G[v].push_back(to);
        else {
          if (leaf[to]) {
            if (c[to])
              gg[v].push_back(n + 10);
            else
              gg[v].push_back(-n - 10);
          } else {
            gg[v].push_back(mxk[to]);
          }
        }
      }
    sort(gg[v].begin(), gg[v].end());
  } else if (ms[v] == -1) {
    if (!leaf[v]) {
      int bl = -n - n - 10 + N, br = n + n + 10 + N;
      while (bl <= br) {
        int m = (bl + br) / 2 - N;
        int r = 0, b = 0;
        for (auto to : g[v]) {
          if (to != pr[v]) {
            if (leaf[to]) {
              if (c[to] == 1)
                b++;
              else
                r++;
            } else {
              if (mxk[to] >= m)
                b++;
              else
                r++;
            }
          }
        }
        if (b - r >= m)
          bl = m + 1 + N;
        else
          br = m - 1 + N;
      }
      mxk[v] = bl - 1 - N;
    }
  } else {
    {
      int bl = -n - n - 10 + N, br = n + n + 10 + N;
      while (bl <= br) {
        int m = (bl + br) / 2 - N;
        int r = 0, b = 0;
        for (auto to : g[v]) {
          if (to != pr[v]) {
            if (ms[to] == -1) {
              if (leaf[to]) {
                if (c[to] == 1)
                  b++;
                else
                  r++;
              } else {
                if (mxk[to] >= m)
                  b++;
                else
                  r++;
              }
            } else {
              if (ms[v] == to) {
                r++;
              } else {
                if (dp0[to] >= m)
                  b++;
                else
                  r++;
              }
            }
          }
        }
        if (b - r >= m)
          bl = m + 1 + N;
        else
          br = m - 1 + N;
      }
      dp0[v] = bl - 1 - N;
    }
    {
      int bl = -n - n - 10 + N, br = n + n + 10 + N;
      while (bl <= br) {
        int m = (bl + br) / 2 - N;
        int r = 0, b = 0;
        for (auto to : g[v]) {
          if (to != pr[v]) {
            if (ms[to] == -1) {
              if (leaf[to]) {
                if (c[to] == 1)
                  b++;
                else
                  r++;
              } else {
                if (mxk[to] >= m)
                  b++;
                else
                  r++;
              }
            } else {
              if (ms[v] == to) {
                b++;
              } else {
                if (dp1[to] >= m)
                  b++;
                else
                  r++;
              }
            }
          }
        }
        if (b - r >= m)
          bl = m + 1 + N;
        else
          br = m - 1 + N;
      }
      dp1[v] = bl - 1 - N;
    }
  }
}
int get(int v) {
  if (leaf[v]) {
    return c[v];
  }
  int b = 0, r = 0;
  int ind = lower_bound(gg[v].begin(), gg[v].end(), k) - gg[v].begin();
  r += ind;
  b += gg[v].size() - ind;
  for (auto to : G[v]) {
    int val = get(ms[to]);
    if (val == 0) {
      if (ms[to] == to) {
        r++;
      } else {
        if (dp0[to] >= k)
          b++;
        else
          r++;
      }
    } else {
      if (ms[to] == to) {
        b++;
      } else {
        if (dp1[to] >= k)
          b++;
        else
          r++;
      }
    }
  }
  return b - r >= k;
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i < n; i++) {
    int v, u;
    scanf("%d%d", &v, &u);
    g[v].push_back(u);
    g[u].push_back(v);
  }
  dfs(1, 0);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &c[i]);
    if (c[i] != -1) leaf[i] = 1;
  }
  scanf("%d", &q);
  while (q) {
    int cnt = min(q, K);
    q -= cnt;
    for (int i = 0; i < cnt; i++) {
      scanf("%d", &type[i]);
      if (type[i] == 2)
        scanf("%d%d", &a[i], &b[i]);
      else
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; i++) {
      ms[i] = -1;
      G[i].clear();
      gg[i].clear();
    }
    for (int i = 0; i < cnt; i++)
      if (type[i] != 3) ms[a[i]] = a[i];
    dfsm(1);
    for (int i = 0; i < cnt; i++) {
      if (type[i] == 3) k = a[i];
      if (type[i] == 2) c[a[i]] = b[i];
      if (type[i] == 1) printf("%d\n", get(a[i]));
    }
  }
  return 0;
}