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 REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define DEBUG(x) cerr << #x << " = " << x << endl
int euler[100000];
int size[100000];
vector<vector<int>> G;
int dfs(int v, int &k) {
  euler[v] = k++;
  size[v] = 1;
  for (int u : G[v]) {
    size[v] += dfs(u, k);
  }
  return size[v];
}
typedef array<int, 10> ten;
const int sqrtN = 512;
//const int sqrtN = 1;
ten multi(ten a, ten b) {
  ten ret;
  for (int i = 0; i < 10; i++) {
    ret[i] = b[a[i]];
  }
  return ret;
}
struct SqrtDecomposition {
  int N, K;
  vector<int> data;
  vector<ten> blockCount;
  vector<bool> lazyFlag;
  vector<ten> lazyUpdate;
  ten initialValue;
  SqrtDecomposition(int n) : N(n) {
    K = (N + sqrtN - 1) / sqrtN;
    data.assign(K * sqrtN, 0);
    lazyFlag.assign(K, false);
    for (int i = 0; i < 10; i++) {
      initialValue[i] = i;
    }
    lazyUpdate.assign(K, initialValue);
    ten zero;
    zero.fill(0);
    zero[0] = sqrtN;
    blockCount.assign(K, zero);
  }
  void eval(int k) {
    if(lazyFlag[k]) {
      lazyFlag[k] = false;
      for (int i = k * sqrtN; i < (k + 1) * sqrtN; i++) {
        data[i] = lazyUpdate[k][data[i]];
      }
      lazyUpdate[k] = initialValue;
    }
  }
  void put(int a, int b, ten perm) {
    for(int k = 0; k < K; ++k) {
      int l = k * sqrtN, r = (k + 1) * sqrtN;
      if(r <= a || b <= l) continue;
      if(a <= l && r <= b) {
        lazyFlag[k] = true;
        lazyUpdate[k] = multi(lazyUpdate[k], perm);
        //cerr << "lazyUpdate[" << k << "] =";
        //for(int i = 0; i < 10; i++) {
        //  cerr << ' ' << lazyUpdate[k][i];
        //}
        //cerr << endl;
        ten cnt;
        cnt.fill(0);
        for(int i = 0; i < 10; i++) {
          cnt[perm[i]] += blockCount[k][i];
        }
        blockCount[k] = cnt;
      }
      else {
        eval(k);
        blockCount[k].fill(0);
        for(int i = max(a, l); i < min(b, r); ++i) {
          data[i] = perm[data[i]];
        }
        for (int i = l; i < min(r, N); ++i) {
          blockCount[k][data[i]]++;
        }
      }
    }
  }
  int get(int a, int b, int x, int y) {
    int ret = 0;
    for(int k = 0; k < K; ++k) {
      int l = k * sqrtN, r = (k + 1) * sqrtN;
      if(r <= a || b <= l) continue;
      if(a <= l && r <= b) {
        for (int i = x; i <= y; i++) {
          // cerr << "blockCount[" << k << "][" << i << "] = " << blockCount[k][i] << endl;
          ret += blockCount[k][i];
        }
      }
      else {
        eval(k);
        for(int i = max(a, l); i < min(b, r); ++i) {
          if(x <= data[i] && data[i] <= y) {
            ret++;
          }
        }
      }
    }
    return ret;
  }
};
signed main() {
  ios::sync_with_stdio(false);
  int N, Q; cin >> N >> Q;
  G.resize(N);
  REP(i,N-1) {
    int u, v; cin >> u >> v;
    G[u].push_back(v);
  }
  int k = 0;
  dfs(0, k);
  SqrtDecomposition sq(N);
  //cerr << "euler =";
  //for(int i = 0; i < N; i++) {
  //  cerr << ' ' << euler[i];
  //}
  //cerr << endl;
  //cerr << "size =";
  //for(int i = 0; i < N; i++) {
  //  cerr << ' ' << size[i];
  //}
  //cerr << endl;
  while(Q--) {
    int t, r, x, y; cin >> t >> r >> x >> y;
    if(t == 2) {
      ten perm;
      for(int i = 0; i < 10; i++) {
        perm[i] = i;
      }
      perm[x] = y;
      sq.put(euler[r], euler[r] + size[r], perm);
    } else {
      int ans = sq.get(euler[r], euler[r] + size[r], x, y);
      // DEBUG(ans);
      cout << ans << endl;
    }
  }
}