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"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;

typedef vector<int> Value1;
typedef vector<short> Value2;
const Value1 Zero1{ 0,0,0,0,0,0,0,0,0,0,1 };
const Value2 Zero2{ 0,1,2,3,4,5,6,7,8,9,10 };

struct Node {
	Value1 sum;//??´??°????????????. ?????????????????§??????????????????????????¨????????????????????????????????????.
	Value2 lazy;	//?????¶???????????????????????????????????????
	Node() :sum(Zero1) {
		lazy = Zero2;
	}
};
int aN, Q;
struct lazy_segtree {
	int N;
	vector<Node>dat;
	lazy_segtree(int n) :N(1) {
		while (N < n) N *= 2;
		dat.resize(2 * N);
		for (int t = N; t < N + aN; ++t) {
			dat[t].sum=vector<int>{ 1,0,0,0,0,0,0,0,0,0,0 };
		}
		for (int i = N - 1; i >= 1; --i) {
			update_node(i);
		}
	}
	void fresh() {
		for (int i = N - 1; i >= 1; --i) {
			update_node(i);
		}
	}

	Value2 lazy_connect(const Value2 l, const Value2 r) {
		Value2 v(l);
		for (int i = 0; i < 11; ++i) {
			v[i]=r[v[i]];
		}
		return v;
	}

	void lazy_func(const int k, const int a, const int b) {
		Value1 next(11);
		for (int i = 0; i < 11; ++i) {
			next[dat[k].lazy[i]]+=dat[k].sum[i];
		}
		dat[k].sum=next;
	}

	Value1 connect(const Value1 l, const Value1 r) {
		Value1 next(l);
		for(int i=0;i<11;++i)next[i]+=r[i];
		return next;
	}

	// inline??????????????¨??§???????????¨????????????!(??????)
	inline void lazy_evaluate_node(int k, int a, int b) {
		lazy_func(k, a, b);
		if (k < N) { // 2*k(???????????????) < 2*N (???????????°) ?????????????????§. ???????????????????????????????????¬???????????¨??????.
			dat[2 * k].lazy = lazy_connect(dat[2 * k].lazy, dat[k].lazy);	//?¬???????????????¬??????????????£?????????.
			dat[2 * k + 1].lazy = lazy_connect(dat[2 * k + 1].lazy, dat[k].lazy);
		}
		dat[k].lazy = Zero2;
	}

	inline void update_node(int k) { // k???????????¢?????????????????????????????¨?????????. ????????\????????¨????????????????????????????????????????????????????????§if???????????????.
		dat[k].sum = connect(dat[2 * k].sum, dat[2 * k + 1].sum);

	}

	// update(l,r,v) := [l,r)?????´??°??????. ?????????0-indexed.
	void update(int l, int r,const Value2& v, int k = 1, int a = 0, int b = -1) {
		if (b == -1)b = N;
		if (l < 0 || r < 0)assert(false);
		lazy_evaluate_node(k, a, b); 	// ??¨?????????????????£???????????????????????????????????§?????¬?????¨???????\?.

		if (b <= l || r <= a) //[a,b)??¨[l,r)???????????????????????´???
			return;
		if (l <= a && b <= r) { // [l,r)???[a,b)????????¨???????????§????????´???
			dat[k].lazy = lazy_connect(dat[k].lazy, v);
			lazy_evaluate_node(k, a, b); //???????????¶???????????¨???????????¨?????????????????§.
			return;
		}

		int m = (a + b) / 2;
		update(l, r, v, 2 * k, a, m);
		update(l, r, v, 2 * k + 1, m, b);
		update_node(k);
	}
	//get(l,r) := [l,r)?????????????????¨?????????????????????. ?????????0-indexed.
	Value1 get(int l, int r, int k = 1, int a = 0, int b = -1) {
		if (b == -1)b = N;

		if (l < 0 || r<0)assert(false);
		lazy_evaluate_node(k, a, b); // ??¨?????????????????£???????????????????????????????????§?????¬?????¨???????\?.

		if (b <= l || r <= a) //[a,b)??¨[l,r)???????????????????????´???
			return Zero1;

		if (l <= a && b <= r) { // [l,r)???[a,b)????????¨???????????§????????´???
			return dat[k].sum;
		}

		int m = (a + b) / 2;
		Value1 vl = get(l, r, 2 * k, a, m);
		Value1 vr = get(l, r, 2 * k + 1, m, b);
		update_node(k);
		return connect(vl, vr);
	}
};

void dfs(const vector<vector<int>>&edges,const int now, const int from, vector<int>&ls, vector<int>&rs, int&id) {
	ls[now]=id;
	id++;
	for (auto e : edges[now]) {
		if(e==from)continue;
		dfs(edges,e,now,ls,rs,id);
	}
	rs[now]=id;
}

int main() {cin>>aN>>Q;
	vector<vector<int>>edges(aN);
	vector<int>ls(aN),rs(aN);
	for (int i = 0; i < aN - 1; ++i) {
		int a,b;cin>>a>>b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	int id=0;
	dfs(edges,0,-1,ls,rs,id);

	lazy_segtree seg(aN);
	
	while(Q--){
		int t,r,x,y;cin>>t>>r>>x>>y;
		if (t == 1) {
			Value1 v1=seg.get(ls[r],rs[r]);
			int ans=accumulate(v1.begin()+x,v1.begin()+y+1,0);
			cout<<ans<<endl;
		}else{
			vector<short>v(11);
			iota(v.begin(),v.end(),0);
			v[x]=y;
			seg.update(ls[r],rs[r],v);
		}
	}
	
	return 0;
}