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;
int read(int &x) { return scanf("%d", &x); }
int read(int &x, int &y) { return scanf("%d%d", &x, &y); }
int read(int &x, int &y, int &z) { return scanf("%d%d%d", &x, &y, &z); }
int read(long long &x) { return scanf("%lld", &x); }
int read(long long &x, long long &y) { return scanf("%lld%lld", &x, &y); }
int read(double &x) { return scanf("%lf", &x); }
char buff[2000010];
int read(string &s) {
  int r = scanf("%s", buff);
  s = buff;
  return r;
}
template <class T, class U>
struct SegmentTree {
  struct Node {
    bool hasCarry = 0;
    int b = 0, e = 0;
    U carry = U();
    T val = T();
    Node() {}
    void join(const Node &l, const Node &r) {
      val = l.val + r.val;
      b = l.b;
      e = r.e;
    }
    void update(const U &u) {
      carry += u;
      u(val);
      hasCarry = 1;
    }
    void pushDown(Node &l, Node &r) {
      if (!hasCarry) return;
      l.update(carry.trim(0, r.e - r.b + 1));
      r.update(carry.trim(l.e - l.b + 1, 0));
      carry = U();
      hasCarry = 0;
    }
  };
  vector<Node> V;
  int N;
  SegmentTree(int N) : V(2 * N), N(N) {}
  template <class I>
  void create(const vector<I> &VEC, int b = 0, int e = -1) {
    if (e == -1) e = N - 1;
    int n = (((b) + (e)) | ((b) != (e)));
    if (b == e) {
      V[n].val = T(VEC[b]), V[n].b = b, V[n].e = e;
    } else {
      int m = (b + e) / 2;
      create(VEC, b, m);
      create(VEC, m + 1, e);
      V[n].join(V[(((b) + (m)) | ((b) != (m)))],
                V[(((m + 1) + (e)) | ((m + 1) != (e)))]);
    }
  }
  T query(int i, int j, int b = 0, int e = -1) {
    if (e == -1) e = N - 1;
    int n = (((b) + (e)) | ((b) != (e)));
    if (i <= b && e <= j) {
      return V[n].val;
    } else {
      int m = (b + e) / 2;
      V[n].pushDown(V[(((b) + (m)) | ((b) != (m)))],
                    V[(((m + 1) + (e)) | ((m + 1) != (e)))]);
      if (i > m) return query(i, j, m + 1, e);
      if (j <= m) return query(i, j, b, m);
      return query(i, j, b, m) + query(i, j, m + 1, e);
    }
  }
  int findOkPrefix(int i, const function<bool(T)> &isOk) {
    static int stk[50];
    int ssz = 0;
    stk[ssz++] = ((((0) + (N - 1)) | ((0) != (N - 1))));
    T acum;
    int sz = 0;
    while (ssz > 0) {
      int t = stk[--ssz];
      Node &n = V[t];
      int m = (n.b + n.e) / 2;
      if (n.e < i) continue;
      T newAcum = sz == 0 ? n.val : (acum + n.val);
      if (i <= n.b) {
        if (isOk(newAcum)) {
          sz += n.e - n.b + 1;
          acum = newAcum;
        } else {
          if (n.b == n.e) return sz;
          n.pushDown(V[(((n.b) + (m)) | ((n.b) != (m)))],
                     V[(((m + 1) + (n.e)) | ((m + 1) != (n.e)))]);
          stk[ssz++] = ((((m + 1) + (n.e)) | ((m + 1) != (n.e))));
          stk[ssz++] = ((((n.b) + (m)) | ((n.b) != (m))));
        }
      } else {
        if (n.b == n.e) continue;
        n.pushDown(V[(((n.b) + (m)) | ((n.b) != (m)))],
                   V[(((m + 1) + (n.e)) | ((m + 1) != (n.e)))]);
        stk[ssz++] = ((((m + 1) + (n.e)) | ((m + 1) != (n.e))));
        stk[ssz++] = ((((n.b) + (m)) | ((n.b) != (m))));
      }
    }
    return sz;
  }
  int findOkSuffix(int j, const function<bool(T)> &isOk) {
    static int stk[50];
    int ssz = 0;
    stk[ssz++] = ((((0) + (N - 1)) | ((0) != (N - 1))));
    T acum;
    int sz = 0;
    while (ssz > 0) {
      int t = stk[--ssz];
      Node &n = V[t];
      int m = (n.b + n.e) / 2;
      if (n.b > j) continue;
      if (n.e <= j) {
        T newAcum = sz == 0 ? n.val : (acum + n.val);
        if (isOk(newAcum)) {
          sz += n.e - n.b + 1;
          acum = newAcum;
        } else {
          if (n.b == n.e) return sz;
          n.pushDown(V[(((n.b) + (m)) | ((n.b) != (m)))],
                     V[(((m + 1) + (n.e)) | ((m + 1) != (n.e)))]);
          stk[ssz++] = ((((n.b) + (m)) | ((n.b) != (m))));
          stk[ssz++] = ((((m + 1) + (n.e)) | ((m + 1) != (n.e))));
        }
      } else {
        if (n.b == n.e) continue;
        n.pushDown(V[(((n.b) + (m)) | ((n.b) != (m)))],
                   V[(((m + 1) + (n.e)) | ((m + 1) != (n.e)))]);
        stk[ssz++] = ((((n.b) + (m)) | ((n.b) != (m))));
        stk[ssz++] = ((((m + 1) + (n.e)) | ((m + 1) != (n.e))));
      }
    }
    return sz;
  }
  void update(int i, int j, const U &v, int b = 0, int e = -1) {
    if (e == -1) e = N - 1;
    int n = (((b) + (e)) | ((b) != (e)));
    if (i <= b && e <= j) {
      V[n].update(v.trim(max(b - i, 0), max(j - e, 0)));
    } else if (i > e || j < b)
      return;
    else {
      int m = (b + e) / 2;
      int l = (((b) + (m)) | ((b) != (m))),
          r = (((m + 1) + (e)) | ((m + 1) != (e)));
      V[n].pushDown(V[l], V[r]);
      update(i, j, v, b, m);
      update(i, j, v, m + 1, e);
      V[n].join(V[l], V[r]);
    }
  }
};
struct MinMax {
  int mn, mx;
  MinMax(int v = 0) : mn(v), mx(v) {}
  MinMax operator+(const MinMax &a) const {
    MinMax r;
    r.mn = min(mn, a.mn);
    r.mx = max(mx, a.mx);
    return r;
  }
};
struct Add {
  int v;
  Add(int v = 0) : v(v) {}
  Add trim(int l, int r) const { return *this; }
  void operator+=(const Add &a) { v += a.v; }
  void operator()(MinMax &a) const {
    a.mn += v;
    a.mx += v;
  }
};
struct HLD {
  int N;
  vector<int> SZ, P, ST, EN, TOP, LVL, PERM;
  vector<vector<int>> adj;
  HLD(int N)
      : N(N), adj(N), PERM(N), SZ(N), P(N), ST(N), EN(N), TOP(N), LVL(N) {}
  void addEdge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  int dfsSZ(int u, int p = -1, int lvl = 0) {
    SZ[u] = 1;
    P[u] = p;
    LVL[u] = lvl;
    int bi = -1;
    for (int i = 0; i < adj[u].size(); ++i) {
      int v = adj[u][i];
      if (v == p) continue;
      SZ[u] += dfsSZ(v, u, lvl + 1);
      if (bi == -1 || SZ[adj[u][bi]] < SZ[v]) bi = i;
    }
    while (bi > 0) swap(adj[u][bi - 1], adj[u][bi]), bi--;
    return SZ[u];
  }
  void dfsDiscovery(int u, int top, int &idx, int p = -1) {
    PERM[idx] = u;
    ST[u] = idx++;
    TOP[u] = top;
    for (int v : adj[u])
      if (v != p) dfsDiscovery(v, (v == adj[u][0]) ? top : v, idx, u);
    EN[u] = idx - 1;
  }
  void build() {
    for (int i = 0, idx = 0; i < N; ++i)
      if (!SZ[i]) dfsSZ(i), dfsDiscovery(i, i, idx);
  }
  int lca(int u, int v) const {
    while (u != -1 && v != -1) {
      if (TOP[u] == TOP[v])
        return LVL[u] <= LVL[v] ? u : v;
      else if (LVL[TOP[u]] > LVL[TOP[v]])
        u = P[TOP[u]];
      else
        v = P[TOP[v]];
    }
    return -1;
  }
  vector<pair<int, int>> lift(int u, int p, bool includeP = true) const {
    vector<pair<int, int>> o;
    while (true) {
      if (TOP[u] == TOP[p]) {
        if (ST[p] + (includeP ? 0 : 1) <= ST[u])
          o.emplace_back(ST[p] + (includeP ? 0 : 1), ST[u]);
        break;
      } else
        o.emplace_back(ST[TOP[u]], ST[u]);
      u = P[TOP[u]];
    }
    return o;
  };
};
struct RedBlueTreee {
  const HLD &H;
  int K, N;
  vector<int> DELTA;
  SegmentTree<MinMax, Add> ST;
  RedBlueTreee(const HLD &H, int K, vector<int> COL)
      : H(H), K(K), DELTA(H.adj.size(), -K), ST(H.adj.size()), N(H.adj.size()) {
    dfs(COL);
    ST.create(DELTA);
  }
  void dfs(vector<int> &COL, int u = 0, int p = -1) {
    if (COL[u] != -1) {
      DELTA[H.ST[u]] = (COL[u] == 0 ? -1 : 1);
      return;
    }
    for (int v : H.adj[u]) {
      if (v == p) continue;
      dfs(COL, v, u);
      DELTA[H.ST[u]] += DELTA[H.ST[v]] >= 0 ? 1 : -1;
    }
  }
  void setColor(int u, int color) {
    auto P = H.lift(u, 0);
    if (color == 0) {
      for (auto p : P) {
        int sz = ST.findOkSuffix(
            p.second, [](const MinMax &m) { return m.mn >= 0 && m.mx <= 1; });
        if (p == P[0] && sz == 0) break;
        if (sz >= p.second - p.first + 1) {
          ST.update(p.first, p.second, -2);
        } else {
          ST.update(p.second - sz, p.second, -2);
          break;
        }
      }
    } else {
      for (auto p : P) {
        int sz = ST.findOkSuffix(
            p.second, [](const MinMax &m) { return m.mn >= -2 && m.mx <= -1; });
        if (p == P[0] && sz == 0) break;
        if (sz >= p.second - p.first + 1) {
          ST.update(p.first, p.second, +2);
        } else {
          ST.update(p.second - sz, p.second, +2);
          break;
        }
      }
    }
  }
  int getColor(int u) { return ST.query(H.ST[u], H.ST[u]).mn >= 0 ? 1 : 0; }
};
struct FatTree {
  const HLD &H;
  vector<int> DELTA;
  vector<int> P;
  vector<int> COL;
  vector<int> SK_CH, BASE_DELTA;
  int K;
  vector<vector<int>> fadj;
  int FAT_SIZE;
  FatTree(const HLD &H, const vector<int> &COL, int K, int FAT_SIZE)
      : FAT_SIZE(FAT_SIZE), H(H), COL(COL), K(K) {
    int N = H.adj.size();
    DELTA = vector<int>(N);
    SK_CH = vector<int>(N);
    BASE_DELTA = vector<int>(N);
    fadj = vector<vector<int>>(N);
    P = vector<int>(N, -1);
    build_dfs();
    computeDelta();
  }
  bool isLeaf(int u) { return u != 0 && H.adj[u].size() == 1; }
  bool isFat(int u) {
    return u == 0 || (H.adj[u].size() > 1 && H.adj[u].size() - 1) >= FAT_SIZE;
  }
  bool isSkinny(int u) { return !isFat(u) && !isLeaf(u); }
  void build_dfs(int u = 0, int p = -1, int pf = -1) {
    if (COL[u] != -1) {
      DELTA[u] = (COL[u] == 0 ? -1 : 1);
      return;
    }
    if (isFat(u) && pf != -1) {
      fadj[pf].push_back(u);
    }
    BASE_DELTA[u] = 0;
    SK_CH[u] = 0;
    for (int v : H.adj[u]) {
      if (v == p) continue;
      build_dfs(v, u, isFat(u) ? u : pf);
      if (isFat(u)) {
        SK_CH[u] += isSkinny(v);
        if (isLeaf(v)) {
          BASE_DELTA[u] += DELTA[v];
          P[v] = u;
        }
      }
    }
  }
  void computeDelta(int u = 0) {
    DELTA[u] = -K + (K > 0 ? -SK_CH[u] : SK_CH[u]) + BASE_DELTA[u];
    for (int v : fadj[u]) {
      computeDelta(v);
      if (H.P[v] == u) {
        DELTA[u] += (DELTA[v] >= 0 ? +1 : -1);
      }
    }
  }
  void setColor(int u, int color) {
    if (COL[u] == color) return;
    COL[u] = color;
    DELTA[u] *= -1;
    if (P[u] != -1) {
      BASE_DELTA[P[u]] += (color == 0) ? -2 : +2;
      computeDelta();
    }
  }
  void setK(int nk) {
    K = nk;
    computeDelta();
  }
  int getColor(int u) { return isSkinny(u) ? (K > 0 ? 0 : 1) : DELTA[u] >= 0; }
};
struct BruteForce {
  vector<vector<int>> adj;
  vector<int> DELTA;
  int K, N;
  BruteForce(vector<vector<int>> adj) : adj(adj), N(adj.size()) {
    DELTA = vector<int>(N);
  }
  void setColor(int u, int c) {
    if (c == 0)
      DELTA[u] = -1000000000;
    else
      DELTA[u] = +1000000000;
  }
  void setK(int c) { K = c; }
  void build(int u = 0, int p = -1) {
    if (u == 0 || adj[u].size() > 1) {
      DELTA[u] = 0;
    }
    for (int v : adj[u]) {
      if (v == p) continue;
      build(v, u);
      DELTA[u] += (DELTA[v] >= K ? +1 : -1);
    }
  }
  int getColor(int u) { return DELTA[u] >= K; }
};
int main() {
  int N, K;
  read(N, K);
  HLD HL(N);
  for (int i = 0; i < N - 1; ++i) {
    int u, v;
    read(u, v);
    u--;
    v--;
    HL.addEdge(u, v);
  }
  HL.build();
  vector<int> COL(N);
  for (int &v : COL) read(v);
  vector<RedBlueTreee> TREES;
  FatTree FT(HL, COL, K, 20);
  for (int i = -20; i <= 20; ++i) {
    TREES.push_back(RedBlueTreee(HL, i, COL));
  }
  int Q;
  read(Q);
  for (int q = 0; q < Q; ++q) {
    int c;
    read(c);
    if (c == 1) {
      int u;
      read(u);
      u--;
      if (abs(K) <= 20) {
        cout << TREES[K + 20].getColor(u) << endl;
      } else {
        cout << FT.getColor(u) << endl;
      }
    } else if (c == 2) {
      int u, c;
      read(u, c);
      u--;
      for (RedBlueTreee &rb : TREES) rb.setColor(u, c);
      FT.setColor(u, c);
    } else {
      int h;
      read(h);
      K = h;
      FT.setK(K);
    }
  }
}