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;
using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;
template <typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const int maxn = 100005;
const int infk = maxn;
const int BSZ = 700;
vector<int> gr[maxn];
vector<int> dead_ends[maxn];
int th[maxn][2];
int threshold[maxn];
int up[maxn], fastup[maxn];
bool isleaf[maxn];
int curcnt[maxn];
int was[maxn];
int curk, curkid;
int n;
int timer;
int c[maxn];
bool isinteresting[maxn];
vector<int> interesting;
pair2<int> qs[BSZ];
vector<int> at[2 * BSZ];
queue<int> q;
int path[maxn];
vector<int> ks;
vector<int> cntdead[2 * BSZ];
int intid[maxn];
vector<int> order;
int newid[maxn];
vector<int> grinit[maxn];
int compk[2 * infk + 5];
void leavedesc(int cur, int pr) {
  newid[cur] = order.size();
  up[newid[cur]] = newid[pr];
  order.push_back(cur);
  for (int i = 0; i < (int)grinit[cur].size(); i++) {
    if (grinit[cur][i] == pr) {
      swap(grinit[cur][i], grinit[cur].back());
      grinit[cur].pop_back();
      i--;
    } else {
      leavedesc(grinit[cur][i], cur);
    }
  }
}
inline void computecolor(int cur) {
  if (was[cur] != timer) curcnt[cur] = 0;
  int cntred = curcnt[cur];
  cntred += (int)cntdead[intid[cur]].size() <= curkid
                ? cntdead[intid[cur]].back()
                : cntdead[intid[cur]][curkid];
  int cntblue = (int)gr[cur].size() - cntred;
  if (cntblue - cntred >= curk)
    c[cur] = 1;
  else
    c[cur] = 0;
}
inline void pushtoparent(int cur) {
  if (cur == 0) return;
  int par = fastup[cur];
  int colorup = 1 - (curk >= th[cur][c[cur]]);
  if (was[par] != timer) {
    was[par] = timer;
    curcnt[par] = 0;
  }
  curcnt[par] += 1 - colorup;
}
int main() {
  scanf("%d%d", &n, &curk);
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    u--, v--;
    grinit[u].push_back(v);
    grinit[v].push_back(u);
  }
  leavedesc(0, -1);
  for (int i = 0; i < n; i++) {
    for (auto t : grinit[i]) gr[newid[i]].push_back(newid[t]);
  }
  for (int i = 0; i < n; i++) scanf("%d", &c[newid[i]]);
  for (int i = 0; i < n; i++)
    if (c[i] != -1) isleaf[i] = true;
  int nq;
  scanf("%d", &nq);
  for (int lq = 0; lq < nq; lq += BSZ) {
    int rq = min(nq, lq + BSZ);
    memset(isinteresting, 0, sizeof isinteresting);
    ks.clear();
    ks.push_back(curk);
    for (int q = lq; q < rq; q++) {
      int t;
      scanf("%d", &t);
      if (t == 1) {
        int v;
        scanf("%d", &v);
        v--;
        v = newid[v];
        isinteresting[v] = true;
        qs[q - lq] = {v, -1};
      } else if (t == 2) {
        int v, newc;
        scanf("%d%d", &v, &newc);
        v--;
        v = newid[v];
        isinteresting[v] = true;
        qs[q - lq] = {v, newc};
      } else {
        int newk;
        scanf("%d", &newk);
        qs[q - lq] = {-1, newk};
        ks.push_back(newk);
      }
    }
    sort((ks).begin(), (ks).end());
    ks.resize(unique((ks).begin(), (ks).end()) - ks.begin());
    int kssz = ks.size();
    ks.push_back(infk);
    int curcompkid = 0;
    for (int i = -infk; i <= infk; i++) {
      compk[i + infk] = curcompkid;
      if (curcompkid < kssz && ks[curcompkid] == i) curcompkid++;
    }
    isinteresting[0] = true;
    interesting.clear();
    for (int i = 0; i <= kssz; i++) at[i].clear();
    for (int cur = 0; cur < n; cur++) {
      dead_ends[cur].clear();
      path[cur] = -1;
      if (isinteresting[cur]) {
        path[cur] = -2;
      }
    }
    for (int cur = n - 1; cur >= 0; cur--) {
      int ret = -1;
      if (isinteresting[cur]) {
        intid[cur] = interesting.size();
        interesting.push_back(cur);
        cntdead[intid[cur]].clear();
        cntdead[intid[cur]].push_back(0);
      }
      if (path[cur] == -1) {
        if (isleaf[cur]) {
          if (c[cur] == 0)
            at[compk[-infk + infk]].push_back(cur);
          else
            at[compk[infk + infk]].push_back(cur);
        } else {
          curcnt[cur] = 0;
          int cntred = 0;
          int cntblue = gr[cur].size();
          at[compk[cntblue - cntred + 1 + infk]].push_back(cur);
        }
      } else if (path[cur] == -2) {
        ret = cur;
      } else {
        ret = path[cur];
      }
      if (cur == 0) break;
      if (ret == -1) continue;
      if (path[up[cur]] == -1)
        path[up[cur]] = ret;
      else if (path[up[cur]] >= 0) {
        isinteresting[up[cur]] = true;
        fastup[path[up[cur]]] = up[cur];
        fastup[ret] = up[cur];
        path[up[cur]] = -2;
      } else {
        fastup[ret] = up[cur];
      }
    }
    timer++;
    for (int i = 0; i <= kssz; i++) {
      for (auto t : at[i]) q.push(t);
      while (!q.empty()) {
        int cur = q.front();
        q.pop();
        if (was[cur] == timer) continue;
        was[cur] = timer;
        if (path[up[cur]] == -1) {
          curcnt[up[cur]]++;
          int cntred = curcnt[up[cur]];
          int cntblue = gr[up[cur]].size() - cntred;
          if (cntblue - cntred + 1 <= ks[i])
            q.push(up[cur]);
          else
            at[compk[cntblue - cntred + 1 + infk]].push_back(up[cur]);
        } else if (path[up[cur]] == -2) {
          int id = intid[up[cur]];
          while ((int)cntdead[id].size() <= i)
            cntdead[id].push_back(cntdead[id].back());
          cntdead[id].back()++;
        } else {
          dead_ends[up[cur]].push_back(ks[i]);
        }
      }
    }
    for (int cur = n - 1; cur >= 0; cur--)
      if (path[cur] != -1) {
        int cntchildren = gr[cur].size();
        if (path[cur] == -2) {
          th[cur][0] = -infk;
          th[cur][1] = +infk;
        } else {
          th[cur][0] = cntchildren + 1;
          th[cur][1] = cntchildren + 1;
          th[cur][0] =
              min(th[cur][0], max(th[path[cur]][0], cntchildren - 1 - 1 + 1));
          th[cur][1] =
              min(th[cur][1], max(th[path[cur]][1], cntchildren - 1 - 1 + 1));
          for (int i = 0; i < (int)dead_ends[cur].size(); i++) {
            int cntred = i + 1;
            int cntblue = cntchildren - cntred;
            th[cur][0] =
                min(th[cur][0], max(dead_ends[cur][i], cntblue - cntred + 1));
            th[cur][1] =
                min(th[cur][1], max(dead_ends[cur][i], cntblue - cntred + 1));
            cntred = i + 1 + 1;
            cntblue = cntchildren - cntred;
            th[cur][0] =
                min(th[cur][0], max(max(th[path[cur]][0], dead_ends[cur][i]),
                                    cntblue - cntred + 1));
            th[cur][1] =
                min(th[cur][1], max(max(th[path[cur]][1], dead_ends[cur][i]),
                                    cntblue - cntred + 1));
          }
          th[path[cur]][0] = th[cur][0];
          th[path[cur]][1] = th[cur][1];
        }
      }
    ::curkid = lower_bound((ks).begin(), (ks).end(), curk) - ks.begin();
    for (int q = 0; q < rq - lq; q++) {
      timer++;
      if (qs[q].first == -1) {
        curk = qs[q].second;
        ::curkid = lower_bound((ks).begin(), (ks).end(), curk) - ks.begin();
      } else if (qs[q].second != -1)
        c[qs[q].first] = qs[q].second;
      else {
        for (auto v : interesting) {
          if (!isleaf[v]) computecolor(v);
          pushtoparent(v);
        }
        printf("%d\n", c[qs[q].first]);
      }
    }
  }
  return 0;
}