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;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

using vi = vector<int>;
const int M = 10;

const vi ZERO(M,0);
vi I(M);

struct LazySegTree{
    int n;
    vector<vi> dat,lazy;
    //初期化
    LazySegTree(int _n){
        n=1;
        while(n<_n) n*=2;
        dat=vector<vi>(2*n-1,ZERO);
        lazy=vector<vi>(2*n-1,I);

        rep(i,_n) dat[i+(n-1)][0] = 1;
        for(int i=n-2; i>=0; --i) dat[i][0] = dat[2*i+1][0]+dat[2*i+2][0];
    }
    void setLazy(int k, const vi &f){
        if(k >= 2*n-1) return;

        vi inv[M];
        rep(i,M) inv[lazy[k][i]].pb(i);

        rep(i,M){
            int nx = f[i];
            for(int j:inv[i]) lazy[k][j] = nx;
        }
    }
    void push(int k, int l, int r){
        if(lazy[k] != I){
            setLazy(2*k+1,lazy[k]);
            setLazy(2*k+2,lazy[k]);
        }

        vi n_dat(ZERO);
        rep(i,M) n_dat[lazy[k][i]] += dat[k][i];
        dat[k] = n_dat;

        lazy[k] = I;
    }
    void fix(int k, int l, int r){
        push(2*k+1,l,r);
        push(2*k+2,l,r);
        rep(i,M) dat[k][i] = dat[2*k+1][i]+dat[2*k+2][i];
    }
    //内部的に投げられるクエリ
    void _change(int a, int b, int k, int l, int r,int x, int y){
        if(r<=a || b<=l) return;
        if(a<=l && r<=b){
            vi f(I);
            f[x] = y;
            setLazy(k,f);
            return;
        }
        push(k,l,r);

        _change(a,b,2*k+1,l,(l+r)/2,x,y);
        _change(a,b,2*k+2,(l+r)/2,r,x,y);

        fix(k,l,r);
    }
    //[a,b)
    void change(int a, int b, int x, int y){
        return _change(a,b,0,0,n,x,y);
    }
    //内部的に投げられるクエリ
    int _count(int a, int b, int k, int l, int r, int x, int y){
        if(r<=a || b<=l) return 0;
        if(a<=l && r<=b){
            push(k,l,r);
            int ret = 0;
            for(int i=x; i<=y; ++i) ret += dat[k][i];
            return ret;
        }
        push(k,l,r);

        int vl=_count(a,b,2*k+1,l,(l+r)/2,x,y);
        int vr=_count(a,b,2*k+2,(l+r)/2,r,x,y);
        return vl+vr;
    }
    //[a,b)
    int count(int a, int b, int x, int y){
        return _count(a,b,0,0,n,x,y);
    }
};


const int N = 100010;
vector<int> G[N];

int L[N],R[N];
int sz = 0;

void dfs(int v, int p){
    L[v] = sz++;
    for(int e:G[v])if(e!=p) dfs(e,v);
    R[v] = sz++;
}

int main(){
    rep(i,M) I[i] = i;

    int n,q;
    scanf(" %d %d", &n, &q);

    rep(i,n-1){
        int u,v;
        scanf(" %d %d", &u, &v);
        G[u].pb(v);
        G[v].pb(u);
    }

    dfs(0,-1);

    LazySegTree s(sz);
    rep(i,q){
        int t,r,x,y;
        scanf(" %d %d %d %d", &t, &r, &x, &y);

        if(t==1) printf("%d\n", s.count(L[r],R[r]+1,x,y)/2);
        else s.change(L[r],R[r]+1,x,y);
    }
    return 0;
}