Problem Statement

On the Paken River, to commemorate the holding of Gijutsushitsu-Oku Programming Contest #5 and to wish for the long continuation of this contest, a lantern floating ceremony is going to be held.
The Paken River has $N$ "checkpoints", numbered from $1$ to $N$.
Checkpoints $A_i$ and $B_i$ are connected by the river without passing through any other checkpoint, and a lantern takes time $C_i$ to flow between them.
Also, checkpoint $1$ is the mouth of the Paken River, and the river flows toward it.
Furthermore, all checkpoints are connected through the river, and the river never branches in the direction of its flow.
In other words, the river has the shape of a rooted tree whose vertices are the checkpoints and whose root is the mouth.
Once a lantern is released from a checkpoint, it travels along the flow of the river, and it goes out when the time specified for that lantern has elapsed since its release.
In the initial plan, no lanterns are released on the river. Answer the following $Q$ queries.

• Add query: add a lantern to be released from checkpoint $v_i$ at time $t_i$. This lantern goes out after $l_i$ units of time.
• Answer query: output the total number of lanterns that can be seen lit at checkpoint $v_i$ by time $t_i$. This includes lanterns that can be seen exactly at time $t_i$, lanterns released from $v_i$, and lanterns that go out exactly when they reach $v_i$ (added at 14:36). In this query, $l_i=0$ always holds.

Input

$N\ Q$
$A_1\ B_1\ C_1$
$A_2\ B_2\ C_2$
$\vdots$
$A_{N-1}\ B_{N-1}\ C_{N-1}$
$type_1\ v_1\ t_1\ l_1$
$type_2\ v_2\ t_2\ l_2$
$\vdots$
$type_Q\ v_Q\ t_Q\ l_Q$

$type_i=0$ denotes an add query, and $type_i=1$ denotes an answer query.

• $2\leq N\leq 50000$
• $1\leq Q\leq 100000$
• $1\leq A_i,B_i,v_i\leq N$
• $0\leq C_i,t_i,l_i\leq 10^{12}$
• $type_i=0,1$
• If $type_i=1$, then $l_i=0$
• The given graph is a tree
• All input values are integers

Output

For each answer query, output on its own line the total number of lanterns that can be seen lit at checkpoint $v_i$ by time $t_i$.

Subtasks

No points are actually awarded, but this problem has several subtasks, on a scale where the full score is 100 points.
Please use them to help your reasoning or for post-contest discussion. Note that the existence of test cases satisfying these constraints is not guaranteed. (added at 15:15)

Subtask 1 (1 point)

• $N,Q\leq 300$

Subtask 2 (15 points)

• $C_i\leq 10^6$, if $type_i=0$ then $t_i\leq 10^6$, if $type_i=1$ then $t_i=10^{12}$

Subtask 3 (27 points)

• $N,Q\leq 2000$

Subtask 4 (57 points)

• No additional constraints.

Sample

3 4
1 2 5
3 1 3
0 2 1 5
0 3 0 4
1 1 5 0
1 1 6 0

1
2

7 9
1 6 4
5 7 1
5 1 7
3 2 4
2 4 3
1 2 5
0 3 1 5
0 4 0 8
0 7 4 2
1 1 7 0
1 1 10 0
0 6 5 5
1 2 7 0
0 4 1 5
1 2 8 0

0
1
2
3