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;

const int backet = 333;

int N, Q;
vector< int > g[100000];
int in[100000], out[100000], ptr;

int sz[(100000 + backet - 1) / backet][10];
int convert[(100000 + backet - 1) / backet][10];
int data[100000];

void tour(int idx, int par = -1)
{
  in[idx] = ptr++;
  for(int &to : g[idx]) if(to != par) tour(to, idx);
  out[idx] = ptr;
}

void push(int k)
{
  for(int i = k * backet; i < min(N, (k + 1) * backet); i++) {
    data[i] = convert[k][data[i]];
  }
  for(int i = 0; i < 10; i++) {
    convert[k][i] = i;
    sz[k][i] = 0;
  }
  for(int i = k * backet; i < min(N, (k + 1) * backet); i++) {
    sz[k][data[i]]++;
  }
}

int main()
{
  cin >> N >> Q;
  for(int i = 1; i < N; i++) {
    int U, V;
    cin >> U >> V;
    g[U].push_back(V);
    g[V].push_back(U);
  }
  tour(0);

  int all = (N + backet - 1) / backet;
  for(int i = 0; i < all; i++) {
    sz[i][0] += min(N, (i + 1) * backet) - i * backet;
    for(int j = 0; j < 10; j++) convert[i][j] = j;
  }

  while(Q--) {
    int t, s, x, y;
    cin >> t >> s >> x >> y;

    int a = in[s], b = out[s];

    if(t == 1) {
      int sum = 0;
      for(int i = 0; i < all; i++) {
        int l = i * backet, r = min(N, (i + 1) * backet);
        if(a >= r || b <= l) continue;
        if(a <= l && r <= b) {
          for(int k = 0; k < 10; k++) {
            if(x <= convert[i][k] && convert[i][k] <= y) sum += sz[i][k];
          }
        } else {
          push(i);
          for(int j = max(a, l); j < min(b, r); j++) {
            if(x <= data[j] && data[j] <= y) sum++;
          }
        }
      }
      cout << sum << endl;
    } else {
      for(int i = 0; i < all; i++) {
        int l = i * backet, r = min(N, (i + 1) * backet);
        if(a >= r || b <= l) continue;
        if(a <= l && r <= b) {
          for(int k = 0; k < 10; k++) {
            if(convert[i][k] == x) convert[i][k] = y;
          }
        } else {
          push(i);
          for(int j = max(a, l); j < min(b, r); j++) {
            if(data[j] == x) {
              data[j] = y;
              --sz[i][x];
              ++sz[i][y];
            }
          }
        }
      }
    }
  }
}