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;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

int n,q;
vi g[125252];
int f[125252][10];
int color[125252];
pair<pii,pii> queries[125252];

const int B = 500;

bool used[125252];
int cnt[125252][10];
vi gg[125252];

void gyudfs(int p,int bef,int par){
  if(used[p]){
    if(p!=0)gg[par].push_back(p);
    par = p;
  }
  cnt[par][color[p]]++;
  for(int to : g[p])if(to!=bef){
    gyudfs(to,p,par);
  }
}

void baadfs(int p,int bef,int par){
  if(used[p]){
    par = p;
  }
  color[p] = f[par][color[p]];
  for(int to : g[p])if(to!=bef){
    baadfs(to,p,par);
  }
}

int countdfs(int p,int x,int y){
  int ret = 0;
  FOR(i,x,y+1)ret += cnt[p][i];
  for(int to : gg[p]){
    ret += countdfs(to,x,y);
  }
  return ret;
}

void changedfs(int p,int x,int y){
  if(x!=y){
    cnt[p][y] += cnt[p][x];
    cnt[p][x] = 0;
  }
  // update f
  REP(i,10)if(f[p][i]==x){
    f[p][i] = y;
  }
  for(int to : gg[p]){
    changedfs(to,x,y);
  }
}

int main(){
  scanf("%d%d",&n,&q);
  REP(i,n-1){
    int u,v;
    scanf("%d%d",&u,&v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  REP(i,q){
    int t,r,x,y;
    scanf("%d%d%d%d",&t,&r,&x,&y);
    queries[i] = make_pair(pii(t,r),pii(x,y));
  }
  int qhead = 0, qtail = 0;
  while(qtail < q){
    qtail += B;
    CHMIN(qtail, q);
    // init
    REP(i,n)REP(j,10)f[i][j] = j,cnt[i][j]=0;
    REP(i,n)used[i]=false, gg[i].clear();
    // shukuyaku
    FOR(i,qhead,qtail){
      int r=queries[i].first.second;
      used[r] = true;
    }
    used[0] = true;
    // REP(i,n)used[i]=true;
    gyudfs(0,-1,0);
    // query
    FOR(i,qhead,qtail){
      int t=queries[i].first.first;
      int r=queries[i].first.second;
      int x=queries[i].second.first;
      int y=queries[i].second.second;
      if(t==1){
        // count
        int ans = countdfs(r,x,y);
        printf("%d\n",ans);
      }else{
        // change
        changedfs(r,x,y);
      }
    }
    // modosu
    baadfs(0,-1,0);
    qhead = qtail;
  }
  return 0;
}