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<iostream>
#include<vector>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<utility>
#include<set>
#include<map>
#include<stack>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll INF = mod * mod;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef vector<int> vec;
typedef long double ld;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define stop char nyaa;cin>>nyaa;

struct SegT {
private:
	int n; vector<vec> node;
	vector<vec> lazy;
	vec e;
public:
	SegT(int sz) {
		n = 1;
		while (n < sz)n <<= 1;
		vec t(10, 0);
		node.resize(2 * n - 1, t);
		e.resize(10);
		rep(i, 10) {
			e[i] = i;
		}
		lazy.resize(2 * n - 1, e);
		rep(i, sz) {
			node[i + n - 1][0]++;
		}
		per(i, n - 1) {
			node[i] = f(node[2 * i + 1], node[2 * i + 2]);
		}
	}
	vec f(vec &a, vec &b) {
		vec ret(10,0);
		rep(i, 10) {
			ret[i] = a[i] + b[i];
		}
		return ret;
	}
	//lazy & lazy
	vec g(vec &a, vec &b) {
		vec ret(10);
		rep(i, 10) {
			ret[i] = a[b[i]];
		}
		return ret;
	}
	void eval(int k, int l, int r) {
		vec nex(10, 0);
		rep(i, 10) {
			nex[lazy[k][i]] += node[k][i];
		}
		node[k] = nex;
		if (r - l > 1) {
			lazy[2 * k + 1] = g(lazy[k], lazy[2 * k + 1]);
			lazy[2 * k + 2] = g(lazy[k], lazy[2 * k + 2]);
		}
		lazy[k] = e;
	}
	void update(int fr, int to, int a, int b, int k = 0, int l = 0, int r = -1) {
		if (r < 0)r = n;
		eval(k, l, r);
		if (r <= a || b <= l)return;
		if (a <= l && r <= b) {
			rep(i, 10) {
				if (lazy[k][i] == fr)lazy[k][i] = to;
			}
			eval(k, l, r);
		}
		else {
			update(fr, to, a, b, k * 2 + 1, l, (l + r) / 2);
			update(fr, to, a, b, k * 2 + 2, (l + r) / 2, r);
			node[k] = f(node[k * 2 + 1], node[k * 2 + 2]);
		}
	}
	int query(int le,int ri,int a, int b, int k = 0, int l = 0, int r = -1) {
		if (r < 0)r = n;
		eval(k, l, r);
		if (r <= a || b <= l)return 0;
		if (a <= l && r <= b) {
			int ret = 0;
			Rep(i, le, ri+1) {
				ret += node[k][i];
			}
			return ret;
		}
		else {
			int vl = query(le,ri,a, b, k * 2 + 1, l, (l + r) / 2);
			int vr = query(le,ri,a, b, k * 2 + 2, (l + r) / 2, r);
			return vl + vr;
		}
	}
	void call() {
		rep(i, 7) {
			query(0, 9, i, i + 1);
			cout << i << endl;
			rep(j, 10) {
				cout << node[i+n-1][j];
			}
			cout << endl;
		}
	}
};

int trans[1 << 17];
int ri[1 << 17];
vector<int> G[1 << 17];

int cur = 0;
void dfs(int id, int fr) {
	trans[id] = cur; cur++;
	rep(j, G[id].size()) {
		int to = G[id][j];
		if (to == fr)continue;
		dfs(to, id);
	}
	ri[trans[id]] = cur;
}

void solve() {
	int n, q; cin >> n >> q;
	rep(i, n-1) {
		int a, b; cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	dfs(0, -1);
	SegT st(n);
	rep(i, q) {
		int t, r, x, y; cin >> t >> r >> x >> y;
		if (t == 1) {
			r = trans[r];
			int ans = st.query(x, y, r, ri[r]);
			cout << ans << endl;
		}
		else {
			r = trans[r];
			st.update(x, y, r, ri[r]);
		}
		//st.call();
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(6);
	solve();
	//stop
		return 0;
}