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>
const int INF = 1e7 + 10;
struct node {
  int Value, Priority, Size, Count;
  node *LeftChild, *RightChild;
  node() {
    Value = Priority = Size = Count = 0;
    LeftChild = RightChild = NULL;
    return;
  }
  node(int _Value) {
    Value = _Value;
    Priority = rand();
    Size = Count = 1;
    LeftChild = RightChild = NULL;
    return;
  }
  inline void Update();
};
struct noneRotateTreap {
  node *Root;
  noneRotateTreap() {
    Root = NULL;
    return;
  }
  inline std::pair<node *, node *> Split(node *Rt, int x);
  inline node *Merge(node *x, node *y);
  inline node *Find(int x);
  inline void Update(int x, int State);
  inline void Insert(int x);
  inline int Delete(int x);
  inline int Rank(int x);
  inline int Query(int x);
  inline int Precursor(int x);
  inline int Successor(int x);
  void Dfs(node *Rt);
  void Debug();
};
inline void node::Update() {
  Size = Count;
  if (LeftChild != NULL) Size += LeftChild->Size;
  if (RightChild != NULL) Size += RightChild->Size;
  return;
}
inline std::pair<node *, node *> noneRotateTreap::Split(node *Rt, int x) {
  if (Rt == NULL) return std::pair<node *, node *>(NULL, NULL);
  if (x < Rt->Value) {
    std::pair<node *, node *> Temp = Split(Rt->LeftChild, x);
    Rt->LeftChild = Temp.second;
    Rt->Update();
    return std::pair<node *, node *>(Temp.first, Rt);
  } else {
    std::pair<node *, node *> Temp = Split(Rt->RightChild, x);
    Rt->RightChild = Temp.first;
    Rt->Update();
    return std::pair<node *, node *>(Rt, Temp.second);
  }
}
inline node *noneRotateTreap::Merge(node *l, node *r) {
  if (l == NULL) return r;
  if (r == NULL) return l;
  if (l->Priority <= r->Priority) {
    l->RightChild = Merge(l->RightChild, r);
    l->Update();
    return l;
  } else {
    r->LeftChild = Merge(l, r->LeftChild);
    r->Update();
    return r;
  }
}
inline node *noneRotateTreap::Find(int x) {
  node *Rt = Root;
  while (Rt) {
    if (Rt->Value == x) return Rt;
    if (x < Rt->Value)
      Rt = Rt->LeftChild;
    else
      Rt = Rt->RightChild;
  }
  return NULL;
}
inline void noneRotateTreap::Update(int x, int State) {
  node *Rt = Root;
  while (Rt) {
    Rt->Size += State;
    if (Rt->Value == x) {
      Rt->Count += State;
      return;
    }
    if (x < Rt->Value)
      Rt = Rt->LeftChild;
    else
      Rt = Rt->RightChild;
  }
  return;
}
inline void noneRotateTreap::Insert(int x) {
  node *T = Find(x);
  if (T != NULL) {
    Update(x, 1);
    return;
  }
  std::pair<node *, node *> Temp = Split(Root, x);
  Temp.first = Merge(Temp.first, new node(x));
  Root = Merge(Temp.first, Temp.second);
  return;
}
inline int noneRotateTreap::Delete(int x) {
  node *T = Find(x);
  if (T == NULL) return 1;
  if (T->Count > 1) {
    Update(x, -1);
    return 0;
  }
  std::pair<node *, node *> Temp1 = Split(Root, x - 1);
  std::pair<node *, node *> Temp2 = Split(Temp1.second, x);
  delete Temp2.first;
  Root = Merge(Temp1.first, Temp2.second);
  return 0;
}
inline int noneRotateTreap::Rank(int x) {
  node *Rt = Root;
  int Ans = 0;
  while (Rt) {
    if (Rt->Value == x)
      return Ans + (Rt->LeftChild ? Rt->LeftChild->Size : 0) + 1;
    if (x < Rt->Value)
      Rt = Rt->LeftChild;
    else
      Ans += (Rt->LeftChild ? Rt->LeftChild->Size : 0) + Rt->Count,
          Rt = Rt->RightChild;
  }
  return Ans + 1;
}
inline int noneRotateTreap::Query(int x) {
  node *Rt = Root;
  while (Rt) {
    if ((Rt->LeftChild ? Rt->LeftChild->Size : 0) < x &&
        x <= (Rt->LeftChild ? Rt->LeftChild->Size : 0) + Rt->Count)
      return Rt->Value;
    if (x <= (Rt->LeftChild ? Rt->LeftChild->Size : 0))
      Rt = Rt->LeftChild;
    else
      x -= (Rt->LeftChild ? Rt->LeftChild->Size : 0) + Rt->Count,
          Rt = Rt->RightChild;
  }
  return 0;
}
inline int noneRotateTreap::Precursor(int x) {
  int Ans = INF;
  node *Rt = Root;
  while (Rt) {
    if (Rt->Value < x)
      Ans = Rt->Value, Rt = Rt->RightChild;
    else
      Rt = Rt->LeftChild;
  }
  return Ans;
}
inline int noneRotateTreap::Successor(int x) {
  int Ans = -INF;
  node *Rt = Root;
  while (Rt) {
    if (Rt->Value > x)
      Ans = Rt->Value, Rt = Rt->LeftChild;
    else
      Rt = Rt->RightChild;
  }
  return Ans;
}
void noneRotateTreap::Debug() {
  Dfs(Root);
  printf("\n");
  return;
}
void noneRotateTreap::Dfs(node *T) {
  if (T == NULL) return;
  Dfs(T->LeftChild);
  for (int i = 1; i <= T->Count; ++i) printf("%d ", T->Value);
  Dfs(T->RightChild);
  return;
}
const int Maxn = 200010;
struct edge {
  int To, Next;
  edge() {}
  edge(int _To, int _Next) : To(_To), Next(_Next) {}
};
edge Edge[Maxn << 1];
int Start[Maxn], Used;
int Num, N, Q, Type, Last, C[Maxn], k;
noneRotateTreap NoneRotateTreap[Maxn];
int CountSon[Maxn];
int Size[Maxn], Father[Maxn], Deep[Maxn], Son[Maxn], Top[Maxn], Dfn[Maxn],
    Ref[Maxn], Bottom[Maxn];
std::pair<int, int> IntervalTree[Maxn << 2];
int TreeSize;
int Record[Maxn];
inline void AddEdge(int x, int y);
inline void CutDfs1(int u, int Fa);
inline void CutDfs2(int u, int Fa);
inline std::pair<int, int> Calc(int x);
inline std::pair<int, int> Merge(std::pair<int, int> x, std::pair<int, int> y);
inline void Update(int Index, int Left, int Right);
inline void BuildIntervalTree(int Index, int Left, int Right);
inline std::pair<int, int> Query(int Index, int Left, int Right, int L, int R);
inline std::pair<int, int> Query(int x);
inline void Modify(int Pos, int &k, int Delta);
inline bool Judge(int Pos, int k, int Delta);
inline void Change(int x, int y);
inline void Modify(int Index, int Left, int Right, int Pos);
int main() {
  srand((unsigned long long)"非旋treap呀");
  scanf("%d%d", &N, &k);
  for (int i = 1; i < N; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    AddEdge(x, y);
    AddEdge(y, x);
  }
  for (int i = 1; i <= N; ++i) scanf("%d", &C[i]);
  scanf("%d", &Q);
  CutDfs1(1, 0);
  Top[1] = 1;
  Dfn[1] = ++TreeSize;
  Ref[TreeSize] = 1;
  CutDfs2(1, 0);
  for (int i = 1; i <= N; ++i)
    Bottom[Top[i]] = std::max(Bottom[Top[i]], Dfn[i]);
  BuildIntervalTree(1, 1, N);
  for (int i = 1; i <= N; ++i)
    if (Top[i] == i) Record[i] = Query(i).first;
  Last = 0;
  for (int i = 1; i <= Q; ++i) {
    int Opt, x, y;
    scanf("%d", &Opt);
    if (Opt == 1) {
      scanf("%d", &x);
      int Ans = Query(x).first > k ? 1 : 0;
      if (Ans == 1) Last = x;
      printf("%d\n", Ans);
    }
    if (Opt == 2) {
      scanf("%d%d", &x, &y);
      Change(x, y);
    }
    if (Opt == 3) scanf("%d", &k);
  }
  return 0;
}
inline void AddEdge(int x, int y) {
  Edge[++Used] = edge(y, Start[x]);
  Start[x] = Used;
  return;
}
inline void CutDfs1(int u, int Fa) {
  Size[u] = 1;
  Father[u] = Fa;
  Deep[u] = Deep[Fa] + 1;
  for (int t = Start[u]; t; t = Edge[t].Next) {
    int v = Edge[t].To;
    if (v == Fa) continue;
    ++CountSon[u];
    CutDfs1(v, u);
    Size[u] += Size[v];
    if (Size[v] > Size[Son[u]]) Son[u] = v;
  }
  return;
}
inline void CutDfs2(int u, int Fa) {
  if (Son[u]) {
    Top[Son[u]] = Top[u];
    Dfn[Son[u]] = ++TreeSize;
    Ref[TreeSize] = Son[u];
    CutDfs2(Son[u], u);
  }
  for (int t = Start[u]; t; t = Edge[t].Next) {
    int v = Edge[t].To;
    if (v == Fa || v == Son[u]) continue;
    Top[v] = v;
    Dfn[v] = ++TreeSize;
    Ref[TreeSize] = v;
    CutDfs2(v, u);
  }
  return;
}
inline std::pair<int, int> Merge(std::pair<int, int> x, std::pair<int, int> y) {
  std::pair<int, int> Ans;
  Ans.first = std::min(std::max(y.first, x.first), x.second);
  Ans.second = std::min(std::max(y.second, x.first), x.second);
  return Ans;
}
inline void Update(int Index, int Left, int Right) {
  if (Left == Right) return;
  IntervalTree[Index] =
      Merge(IntervalTree[Index << 1], IntervalTree[Index << 1 | 1]);
  return;
}
inline void BuildIntervalTree(int Index, int Left, int Right) {
  if (Left == Right) {
    Modify(1, 1, N, Left);
    if (Top[Ref[Left]] == Ref[Left]) {
      NoneRotateTreap[Father[Ref[Left]]].Insert(Query(Ref[Left]).first);
    }
    return;
  }
  int Mid = (Left + Right) >> 1;
  BuildIntervalTree(Index << 1 | 1, Mid + 1, Right);
  BuildIntervalTree(Index << 1, Left, Mid);
  Update(Index, Left, Right);
  return;
}
inline std::pair<int, int> Query(int Index, int Left, int Right, int L, int R) {
  if (L <= Left && Right <= R) return IntervalTree[Index];
  int Mid = (Left + Right) >> 1;
  if (R <= Mid) return Query(Index << 1, Left, Mid, L, R);
  if (L > Mid) return Query(Index << 1 | 1, Mid + 1, Right, L, R);
  return Merge(Query(Index << 1, Left, Mid, L, R),
               Query(Index << 1 | 1, Mid + 1, Right, L, R));
}
inline std::pair<int, int> Calc(int x) {
  if (C[x] == 0) return std::pair<int, int>(-INF, -INF);
  if (C[x] == 1) return std::pair<int, int>(INF, INF);
  std::pair<int, int> Ans = std::pair<int, int>(0, 0);
  Modify(x, Ans.first, 2);
  Modify(x, Ans.second, 0);
  return Ans;
}
inline std::pair<int, int> Query(int x) {
  return Query(1, 1, N, Dfn[x], Bottom[Top[x]]);
}
inline void Modify(int Pos, int &k, int Delta) {
  while (!Judge(Pos, k, Delta)) ++k;
  while (Judge(Pos, k - 1, Delta)) --k;
  return;
}
inline bool Judge(int Pos, int k, int Delta) {
  int m = CountSon[Pos] - k - Delta;
  int c = NoneRotateTreap[Pos].Rank(k + 1) - 1;
  return m - 2 * c < 0;
}
inline void Change(int x, int y) {
  C[x] = y;
  while (x) {
    Modify(1, 1, N, Dfn[x]);
    NoneRotateTreap[Father[Top[x]]].Delete(Record[Top[x]]);
    NoneRotateTreap[Father[Top[x]]].Insert(Record[Top[x]] =
                                               Query(Top[x]).first);
    x = Father[Top[x]];
  }
  return;
}
inline void Modify(int Index, int Left, int Right, int Pos) {
  if (Left == Right) {
    IntervalTree[Index] = Calc(Ref[Pos]);
    return;
  }
  int Mid = (Left + Right) >> 1;
  if (Pos <= Mid) Modify(Index << 1, Left, Mid, Pos);
  if (Pos > Mid) Modify(Index << 1 | 1, Mid + 1, Right, Pos);
  Update(Index, Left, Right);
  return;
}