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 <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <functional>
#include <iostream>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

class node{
public:
	int sum[11];
	int lazy[11];
	node(){
		for(int i=0;i<10;i++){
			sum[i]=0;
			lazy[i]=0;
		}
	}
};

int n,q;
int f[100001],t[100001];
vector<int> G[100001];
bool used[100001];
node seg[1<<20];
int cnt=0;
int wid=1;

void dfs(int v){
	used[v]=true;
	f[v]=cnt++;
	for(int i=0;i<G[v].size();i++){
		if(!used[G[v][i]]){
			dfs(G[v][i]);
		}
	}
	t[v]=cnt++;
}

int tmp[11];

inline void lazy_evaluate_node(int k){
	memset(tmp,0,sizeof(tmp));
	for(int i=0;i<10;i++){
		tmp[seg[k].lazy[i]]+=seg[k].sum[i];
	}
	for(int i=0;i<10;i++){
		seg[k].sum[i]=tmp[i];
	}
	if(k+1<wid){
		for(int i=0;i<10;i++){
			tmp[i]=seg[k*2+1].lazy[i];
		}
		for(int i=0;i<10;i++){
			seg[k*2+1].lazy[i]=seg[k].lazy[tmp[i]];
		}
		for(int i=0;i<10;i++){
			tmp[i]=seg[k*2+2].lazy[i];
		}
		for(int i=0;i<10;i++){
			seg[k*2+2].lazy[i]=seg[k].lazy[tmp[i]];
		}
	}
	for(int i=0;i<10;i++){
		seg[k].lazy[i]=i;
	}
}

inline void lazy_update_node(int k){
	for(int i=0;i<10;i++){
		seg[k].sum[i]=seg[k*2+1].sum[i]+seg[k*2+2].sum[i];
	}
}

void add(int k,int a){
	k+=wid-1;
	seg[k].sum[0]+=a;
	while(k>0){
		k=(k-1)/2;
		seg[k].sum[0]=seg[k*2+1].sum[0]+seg[k*2+2].sum[0];
	}
}

void update(int f,int t,int a,int b,int k=0,int l=0,int r=wid){
	lazy_evaluate_node(k);
	if(r<=a || b<=l)return;
	if(a<=l && r<=b){
		seg[k].lazy[f]=t;
		lazy_evaluate_node(k);
		return;
	}
	update(f,t,a,b,k*2+1,l,(l+r)/2);
	update(f,t,a,b,k*2+2,(l+r)/2,r);
	lazy_update_node(k);
}

int query(int x,int y,int a,int b,int k=0,int l=0,int r=wid){
	lazy_evaluate_node(k);
	if(r<=a || b<=l)return 0;
	if(a<=l && r<=b){
		int res=0;
		for(int i=x;i<=y;i++){
			res+=seg[k].sum[i];
		}
		return res;
	}
	int vl=query(x,y,a,b,k*2+1,l,(l+r)/2);
	int vr=query(x,y,a,b,k*2+2,(l+r)/2,r);
	lazy_update_node(k);
	return vl+vr;
}

int main(void){
	scanf("%d%d",&n,&q);
	for(int i=0;i<n-1;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
	}
	memset(used,false,sizeof(used));
	dfs(0);
	while(wid<cnt+1)wid*=2;
	for(int i=0;i<wid*2-1;i++){
		for(int j=0;j<10;j++){
			seg[i].sum[j]=0;
		}
	}
	for(int i=0;i<n;i++){
		add(f[i],1);
	}
	for(int i=0;i<q;i++){
		int type,r,x,y;
		scanf("%d%d%d%d",&type,&r,&x,&y);
		if(type==1){
			int res=query(x,y,f[r],t[r]);
			printf("%d\n",res);
		}else{
			update(x,y,f[r],t[r]);
		}
	}
	return 0;
}