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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 600001


int N = 1;
int euler_index,root;
int num_count[NUM][10],change_table[NUM][10];
int LEFT[100000],RIGHT[100000];
vector<int> G[100000];


void init(int first_N){
	while(N < first_N)N *= 2;
}

//最初、全ての電球の明るさは0
void add(int loc){
	loc += N-1;

	num_count[loc][0] += 1;

	while(loc > 0){
		loc = (loc-1)/2;
		num_count[loc][0] = num_count[2*loc+1][0]+num_count[2*loc+2][0];
	}
}

void update_array(int node_id,int next_array[10]){

	//★★まとめて変更する場合は、まとめて処理する★★
	int next_count[10];
	for(int i = 0; i <= 9; i++)next_count[i] = 0;

	for(int i = 0; i <= 9; i++){
		next_count[next_array[i]] += num_count[node_id][i];
	}
	int next_change_table[10];
	for(int i = 0; i <= 9; i++){
		next_change_table[i] = next_array[change_table[node_id][i]];
	}

	for(int i = 0; i <= 9; i++){
		num_count[node_id][i] = next_count[i];
		change_table[node_id][i] = next_change_table[i];
	}
}


void update(int update_left,int update_right,int node_id,int node_left,int node_right,int x,int y){

	if(update_right < node_left || update_left > node_right)return; //範囲外なら何もしない
	else if(update_left <= node_left && update_right >= node_right){ //このノードのカバー区間が、更新区間の部分区間である場合

		for(int i = 0; i <= 9; i++){
			if((change_table[node_id][i] == x)){
				change_table[node_id][i] = y; //変換対応を更新
			}
		}
		num_count[node_id][y] += num_count[node_id][x]; //★★iをyに足すのは間違い!xを足す★★
		num_count[node_id][x] = 0;

		return; //更新は子方向に伝えない

	}else{
		//このノードのカバー範囲と更新範囲に部分的な重なりがある場合
		//現在自分が★蓄積していた(子供に伝えていなかった)★変換情報を子に投げる(★★更新区間が、node_left～node_rightであることに注意★★)
		update_array(2*node_id+1,change_table[node_id]);
		update_array(2*node_id+2,change_table[node_id]);

		//情報を伝えたので変換表をリセット
		for(int i = 0; i <= 9; i++){
			change_table[node_id][i] = i;
		}

		//改めて今回のクエリを投げる
		update(update_left,update_right,2*node_id+1,node_left,(node_left+node_right)/2,x,y);
		update(update_left,update_right,2*node_id+2,(node_left+node_right)/2+1,node_right,x,y);

		//★★子にクエリを投げた結果、このノードの以下の集計が変わるので、ボトムアップ的に再帰的に計算する
		for(int i = 0; i <= 9; i++){
			num_count[node_id][i] = num_count[2*node_id+1][i]+num_count[2*node_id+2][i];
		}
	}
}




int getSum(int search_left,int search_right,int node_id,int node_left,int node_right,int x,int y){
	if(search_right < node_left || search_left > node_right){
		return 0;
	}else if(search_left <= node_left && search_right >= node_right){

		int ret = 0;
		for(int i = x; i <= y; i++){
			ret += num_count[node_id][i];
		}

		return ret;

	}else{

		//★★貯めていた情報を下に伝える★★
		update_array(2*node_id+1,change_table[node_id]);
		update_array(2*node_id+2,change_table[node_id]);

		//情報を伝えたので変換表をリセット
		for(int i = 0; i <= 9; i++){
			change_table[node_id][i] = i;
		}

		//★★自分より下の、数の個数情報は、updateの際に把握しているので変更不要★★

		int left = getSum(search_left,search_right,2*node_id+1,node_left,(node_left+node_right)/2,x,y);
		int right = getSum(search_left,search_right,2*node_id+2,(node_left+node_right)/2+1,node_right,x,y);
		return left+right;
	}
}


//オイラーツアーで、ノードのカバー範囲を計算する
void euler_tour(int node_id,int pre_node){
	LEFT[node_id] = euler_index++;

	for(int i = 0; i < G[node_id].size(); i++){
		if(G[node_id][i] == pre_node)continue;
		euler_tour(G[node_id][i],node_id);
	}
	RIGHT[node_id] = euler_index++;
}

int main(){

	euler_index = 0;
	root = 0;

	int V,Q;
	scanf("%d %d",&V,&Q);

	int from,to;

	for(int loop = 0; loop < V-1; loop++){
		scanf("%d %d",&from,&to);
		G[from].push_back(to);
		G[to].push_back(from);
	}

	euler_tour(root,-1);

	int first_N = RIGHT[root]+1; //セグ木における最下層のノードは、最低RIGHT[root]+1個あれば良い(+1は0オリジンのため)

	init(first_N);

	//変換配列および集計配列の初期化
	for(int i = 0; i <= 2*N-2; i++){
		for(int k = 0; k <= 9; k++){
			num_count[i][k] = 0;
			change_table[i][k] = k;
		}
	}

	//有効ノードの個数を、セグメント木に反映させる
	for(int i = 0; i < V; i++){
		add(LEFT[i]);
	}

	int command,node_id,x,y;

	for(int loop = 0; loop < Q; loop++){

		scanf("%d %d %d %d",&command,&node_id,&x,&y);

		if(command == 1){ //計上

			printf("%d\n",getSum(LEFT[node_id],RIGHT[node_id],0,0,N-1,x,y));

		}else{ //更新

			if(x == y)continue;

			update(LEFT[node_id],RIGHT[node_id],0,0,N-1,x,y);
		}
	}

	return 0;
}