Submit
 

I : Tree-Light

Time Limit : 2 sec, Memory Limit : 262142 KB

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が接点uiを上にして、接点uiと接点viを繋ぐことを表す。
n+1行目以降のq行にはあなたのとる行動が空白区切りで与えられる。ti = 1ならcount(ri, xi, yi)を、ti = 2ならchange(ri, xi, yi)を表す。

Constraints

  • 1 ≤ n ≤ 105
  • 1 ≤ q ≤ 105
  • 0 ≤ ui, vi, ri ≤ n−1 (ui ≠ vi)
  • 0 ≤ xi, yi ≤ 9 (ti = 1の時xi ≤ yi)

Output

count(ri, xi, yi)について、その答えを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