Problem: Problem

You bought a tree-shaped lighting fixture called a tree light.

This luminaire has n contacts, each numbered from 0 to n-1. Each contact consists of a light bulb that can express 10 levels of brightness and a device for switching the state of the light bulb. Initially, the brightness of the bulbs at all contacts is zero.

In addition, there is a cable wire between the contacts. All contacts are connected by n-1 cable lines and are hung with contact 0 facing up. Here, a set of contacts connected to the contact i via zero or more cable wires downward from the contact i is called a subtree rooted at the contact i.

You take one of the following actions with respect to this luminaire:

* count (r, x, y): Counts the number of light bulbs with a brightness of x or more and y or less among the light bulbs of the contact contained in the subtree rooted at the contact r.
* change (r, x, y): Change the brightness of all the bulbs of the contacts contained in the subtree rooted at the contact r to y, whose brightness is exactly x.



Since q actions are given, output the number of light bulbs at that time each time count (r, x, y) is given.

Constraints

* 1 ≤ n ≤ 105
* 1 ≤ q ≤ 105
* 0 ≤ ui, vi, ri ≤ n−1 (ui ≠ vi)
* 0 ≤ xi, yi ≤ 9 (when ti = 1 xi ≤ yi)

Input

The input is given in the following format.


n q
u1 v1
u2 v2
...
un−1 vn−1
t1 r1 x1 y1
t2 r2 x2 y2
...
tq rq xq yq


The number of contacts n that make up the tree light and the number of actions you take q are given on the first line, separated by blanks.
Cable line information is given on the following n-1 line, separated by blanks. The information of the i-th cable line indicates that the cable line i connects the contact ui and the contact vi with the contact ui facing up.
n & plus; The actions you take are given in the q lines after the first line, separated by blanks. If ti = 1, it represents count (ri, xi, yi), and if ti = 2, it represents change (ri, xi, yi).

Output

For each count (ri, xi, yi), output the answer on one line.

Examples

Input

7 5
0 1
1 2
1 3
0 4
4 5
4 6
1 0 0 9
2 0 0 5
2 1 5 8
1 0 5 8
1 0 8 8


Output

7
7
3


Input

7 5
0 1
1 2
2 3
0 4
4 5
5 6
2 1 0 5
2 4 0 6
2 3 5 6
2 5 6 5
1 0 0 5


Output

5

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;

/*
struct Monoid {
  using T = _type_;
  static T op(const T& a, const T& b) {return _a_op_b_;}
  static constexpr T e() {return _identity_element_;};
};
*/

/*
struct M_act {
  using OS = _operand_set_(i.e. Monoid)_;
  using OM = _operator_monoid_(i.e. Monoid)_;
  using T = OS::T;
  using M = OM::T;
  static T act(const int& len, const M& m, const T& a) {return _m_act_a_}
};
*/

template<class M_act>
struct RUSegmentTree {
  using OS = typename M_act::OS;
  using OM = typename M_act::OM;
  using T = typename OS::T;
  using M = typename OM::T;
  vector<T> data;
  vector<M> lazy;
  int sz;
  RUSegmentTree(){}
  RUSegmentTree(int n){init(n);}
  RUSegmentTree(vector<T> _data) {
    init(_data.size());
    build(_data);
  }
  void init(int n) {
    sz = 1; while(sz < n) sz <<= 1;
    data.resize(2*sz-1, OS::e());
    lazy.resize(2*sz-1, OM::e());
  }
  void build(const vector<T>& _data) {
    for(int i = 0; i < (int)_data.size(); ++i) data[i+sz-1] = _data[i];
    for(int i = sz-2; i >= 0; --i) data[i] = OS::op(data[2*i+1], data[2*i+2]);
  }
  void push(int k, int len) {
    if(lazy[k] == OM::e()) return;
    if(len > 1) {
      lazy[2*k+1] = OM::op(lazy[k], lazy[2*k+1]);
      lazy[2*k+2] = OM::op(lazy[k], lazy[2*k+2]);
    }
    data[k] = M_act::act(len, lazy[k], data[k]);
    lazy[k] = OM::e();
  }
  void update(int a, int b, const M& x, int k, int l, int r) {
    push(k, r-l);
    if(r <= a || b <= l) return;
    if(a <= l && r <= b) {
      lazy[k] = OM::op(x, lazy[k]);
      push(k, r-l);
      return;
    }
    update(a, b, x, 2*k+1, l, (l+r)/2);
    update(a, b, x, 2*k+2, (l+r)/2, r);
    data[k] = OS::op(data[2*k+1], data[2*k+2]);
  }
  void update(int a, int b, const T& x) {
    update(a, b, x, 0, 0, sz);
  }
  T query(int a, int b, int k, int l, int r) {
    push(k, r-l);
    if(r <= a || b <= l) return OS::e();
    if(a <= l && r <= b) return data[k];
    T vl = query(a, b, 2*k+1, l, (l+r)/2);
    T vr = query(a, b, 2*k+2, (l+r)/2, r);
    return OS::op(vl, vr);
  }
  T query(int a, int b) {
    return query(a, b, 0, 0, sz);
  }
};

struct Data {
  using T = array<int, 10>;
  static T op(const T& a, const T& b) {
    T res = e();
    for(int i = 0; i < 10; ++i) res[i] = a[i]+b[i];
    return res;
  }
  static T e() {
    static T ini = array<int, 10>{0};
    return ini;
  }
};

struct Operator {
  using T = array<int, 10>;
  static T op(const T& a, const T& b) {
    T res = e();
    for(int i = 0; i < 10; ++i) {
      res[i] = a[b[i]];
    }
    return res;
  }
  static T e() {
    static T ini = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    return ini;
  }
};

struct TreeLightMonoid {
  using OS = Data;
  using OM = Operator;
  using T = OS::T;
  using M = OM::T;
  static T act(const int& len, const M& m, const T& a) {
    T res = OS::e();
    for(int i = 0; i < 10; ++i) {
      res[m[i]] += a[i];
    }
    return res;
  }
};

using Graph = vector<vector<int> >;

int main() {
  int n, q;
  cin >> n >> q;
  Graph graph(n);
  for(int i = 0; i < n-1; ++i) {
    int u, v;
    cin >> u >> v;
    graph[u].push_back(v);
  }

  vector<int> L(n), R(n);
  int idx = 0;
  function<void(int)> dfs = [&](int u) {
    L[u] = idx++;
    for(int v : graph[u]) dfs(v);
    R[u] = idx;
  };
  dfs(0);

  vector<array<int, 10> > data(n, array<int, 10>{1, 0});
  RUSegmentTree<TreeLightMonoid> seg(data);
  while(q--) {
    int t, r, x, y;
    cin >> t >> r >> x >> y;
    if(t == 1) {
      auto res = seg.query(L[r], R[r]);
      int ans = 0;
      for(int i = x; i <= y; ++i) {
	ans += res[i];
      }
      cout << ans << endl;
    } else {
      auto tmp = Operator::e();
      tmp[x] = y;
      seg.update(L[r], R[r], tmp);
    }
  }

  return 0;
}