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;

#define int long long
#define all(v) begin(v), end(v)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for(int i = (int)(s); i < (int)(n); i++)
#define min(...) min({__VA_ARGS__})
#define max(...) max({__VA_ARGS__})

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using pint = pair<int, int>;
using tint = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

#define MAX_N 100000
#define MAX_Q 100000

struct SegmentTree {
  vector< array<int, 10> > data, lazy;
  array<int, 10> ini{{0,1,2,3,4,5,6,7,8,9}};
  int sz;
  SegmentTree(){}
  SegmentTree(int n) {
    sz = 1; while(sz < n) sz <<= 1;
    data.resize(2*sz-1, array<int, 10>{0});
    lazy.resize(2*sz-1, ini);
    rep(i, n) data[i+sz-1][0] = 1;
    for(int k = sz-2; k >= 0; k--)
      data[k][0] = data[2*k+1][0] + data[2*k+2][0];
  }
  void push(int k, int l, int r) {
    int tmp[10];
    rep(i, 10) tmp[i] = data[k][i], data[k][i] = 0;
    rep(i, 10) data[k][lazy[k][i]] += tmp[i];
    if(r - l > 1) {
      array<int, 10> conv = ini;
      rep(i, 10) conv[i] = lazy[k][i];
      rep(i, 10) {
	lazy[2*k+1][i] = conv[lazy[2*k+1][i]];
	lazy[2*k+2][i] = conv[lazy[2*k+2][i]];
      }
    }
    lazy[k] = ini;
  }
  void update(int a, int b, int x, int y, int k, int l, int r) {
    push(k, l, r);
    if(r <= a || b <= l) return;
    if(a <= l && r <= b) {
      rep(i, 10) if(lazy[k][i] == x) lazy[k][i] = y;
      push(k, l, r);
      return;
    }
    update(a, b, x, y, 2*k+1, l, (l+r)/2);
    update(a, b, x, y, 2*k+2, (l+r)/2, r);
    rep(i, 10) data[k][i] = data[2*k+1][i] + data[2*k+2][i];
  }
  void update(int a, int b, int x, int y) {
    update(a, b, x, y, 0, 0, sz);
  }
  int query(int a, int b, int x, int y, int k, int l, int r) {
    push(k, l, r);
    if(r <= a || b <= l) return 0;
    if(a <= l && r <= b) {
      int res = 0;
      for(int i = x; i <= y; i++) res += data[k][i];
      return  res;
    }
    int vl = query(a, b, x, y, 2*k+1, l, (l+r)/2);
    int vr = query(a, b, x, y, 2*k+2, (l+r)/2, r);
    return vl + vr;
  }
  int query(int a, int b, int x, int y) {
    return query(a, b, x, y, 0, 0, sz);
  }
};

int n, q;
vector<int> graph[MAX_N];
int li[MAX_N], ri[MAX_N], idx;

SegmentTree seg;

void dfs(int u) {
  li[u] = idx++;
  for(int v : graph[u]) dfs(v);
  ri[u] = idx;
}

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  cin >> n >> q;
  rep(i, n-1) {
    int u, v;
    cin >> u >> v;
    graph[u].push_back(v);
  }
  memset(li, -1, sizeof(li));
  memset(ri, -1, sizeof(ri));
  idx = 0;
  dfs(0);

  seg = SegmentTree(n);
  rep(i, q) {
    int t, r, x, y;
    cin >> t >> r >> x >> y;
    if(t == 1) cout << seg.query(li[r], ri[r], x, y) << endl;
    else seg.update(li[r], ri[r], x, y);
  }

  return 0;
}