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 MAX_N 100005

struct data{
  int p[10];
};

data A,B;

#define SZ (1<<17)

struct segtree{
  data t[SZ*2];
  data u[SZ*2];
  void init(int k=0,int l=0,int r=SZ){
    for(int i=0;i<10;i++){
      t[k].p[i]=0;
      u[k].p[i]=i;
    }
    
    if(r-l==1){
      t[k].p[0]=1;
      return;
    }
    
    int m=(l+r)/2;
    init(k*2+1,l,m);
    init(k*2+2,m,r);
    for(int i=0;i<10;i++){
      t[k].p[i]+=t[k*2+1].p[i];
      t[k].p[i]+=t[k*2+2].p[i];
    }
  }
  
  void add(data &td,data &ud,data &x){
    int tt[10];
    int uu[10];
    for(int i=0;i<10;i++){
      tt[i]=0;
      uu[i]=i;
    }
    for(int i=0;i<10;i++){
      tt[ x.p[i] ]+=td.p[i];
      uu[i]=x.p[ ud.p[i] ];
    }
    for(int i=0;i<10;i++){
      td.p[i]=tt[i];
      ud.p[i]=uu[i];
    }
  }
  
  
  void compute(int k,int l,int r){
    if(r-l==1)return;
    int L=k*2+1;
    int R=k*2+2;

    add(t[L],u[L],u[k]);
    add(t[R],u[R],u[k]);
    
    for(int i=0;i<10;i++){
      t[k].p[i]=t[L].p[i]+t[R].p[i];
      u[k].p[i]=i;
    }
  }

  data Get(int a,int b,int k=0,int l=0,int r=SZ){
    if(b<=l || r<=a)return A;
    compute(k,l,r);
    if(a<=l && r<=b){
      return t[k];
    }else{
      int m=(l+r)/2;
      data lc=Get(a,b,k*2+1,l,m);
      data rc=Get(a,b,k*2+2,m,r);
      for(int i=0;i<10;i++)lc.p[i]+=rc.p[i];
      return lc;
    }
  }
  
  void dfs(int a,int b,data d,int k=0,int l=0,int r=SZ){
    if(b<=l || r<=a)return;
    compute(k,l,r);
    if(a<=l && r<=b){
      add(t[k],u[k],d);
    }else{
      int m=(l+r)/2;
      dfs(a,b,d,k*2+1,l,m);
      dfs(a,b,d,k*2+2,m,r);
      for(int i=0;i<10;i++)
        t[k].p[i]=t[k*2+1].p[i]+t[k*2+2].p[i];
    }
  }
};

int N,Q;
vector<int> G[MAX_N];
int v[MAX_N],size[MAX_N],cc=0;

void dfs(int pos){
  v[pos]=cc++;
  size[pos]=1;
  for(int i=0;i<(int)G[pos].size();i++){
    int to=G[pos][i];
    dfs(to);
    size[pos]+=size[to];
  }
}


segtree T;
int main(){
  for(int i=0;i<10;i++){
    A.p[i]=0;
    B.p[i]=i;
  }
  
  scanf("%d %d",&N,&Q);
  for(int i=0;i<N-1;i++){
    int a,b;
    scanf("%d %d",&a,&b);
    G[a].push_back(b);
  }
  
  dfs(0);
  T.init();
  
  while(Q--){
    int type;
    int r,x,y;
    scanf("%d %d %d %d",&type,&r,&x,&y);
    
    if(type==1){
      data key=T.Get(v[r],v[r]+size[r]);
      int sum=0;
      for(int i=x;i<=y;i++)sum+=key.p[i];
      printf("%d\n",sum);
    }else if(type==2){
      data key;
      for(int i=0;i<10;i++)key.p[i]=i;
      key.p[x]=y;
      T.dfs(v[r],v[r]+size[r],key);
    }

  }
  return 0;
}