Problem I: Tree-Light

Problem

あなたはツリーライトというツリー状の照明器具を買ってきた。

この照明器具にはn個の接点があり、それぞれ0からn−1までの番号がついている。各接点は10段階の明るさを表現できる電球と、電球の状態を切り替えるための装置で構成されている。最初、すべての接点の電球の明るさは0である。

また、接点と接点の間にはケーブル線がある。すべての接点はn−1本のケーブル線によって繋がれており、接点0を上にして吊り下げられる。ここで、接点iから下方向に0本以上のケーブル線を介して、接点iと繋がる接点の集合を、接点iを根とした部分木と呼ぶ。

あなたはこの照明器具に対し、以下のいずれかの行動をとる。

• count(r, x, y): 接点rを根とした部分木に含まれる接点の電球の中で、明るさがx以上y以下になっている電球の数を数える。
• change(r, x, y): 接点rを根とした部分木に含まれる接点の電球の中で、明るさがちょうどxになっているすべての電球の明るさをyに変更する。

q回の行動が与えられるので、count(r, x, y)が与えられるたびにその時点での電球の数を出力せよ。

Input

入力は以下の形式で与えられる。

n q
u1 v1
u2 v2
...
un−1 vn−1
t1 r1 x1 y1
t2 r2 x2 y2
...
tq rq xq yq

1行目にツリーライトを構成する接点の数n、あなたのとる行動の数qが空白区切りで与えられる。
続くn−1行にはケーブル線の情報が空白区切りで与えられる。i番目のケーブル線の情報は、ケーブル線iが接点u_iを上にして、接点u_iと接点v_iを繋ぐことを表す。
n+1行目以降のq行にはあなたのとる行動が空白区切りで与えられる。t_i = 1ならcount(r_i, x_i, y_i)を、t_i = 2ならchange(r_i, x_i, y_i)を表す。

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ q ≤ 10⁵
• 0 ≤ u_i, v_i, r_i ≤ n−1 (u_i ≠ v_i)
• 0 ≤ x_i, y_i ≤ 9 (t_i = 1の時x_i ≤ y_i)

Output

各count(r_i, x_i, y_i)について、その答えを1行に出力する。

Sample Input 1

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

Sample Output 1

7
7
3

Sample Input 2

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

Sample Output 2

5