F. The Lorax
time limit per test
10 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

I am the Lorax, and I speak for the Trees!

Plant many of them, plant many now please,

We all live in Thneedville, a connected component,

that has $$$n$$$ nodes and $$$n-1$$$ edges this moment,

$$$q$$$ times we'll make $$$x_i$$$ seeds and the same number of pots,

but in different places, believe it or nots.

Match each seed with a pot, and each pot with a seed

But match in a way that's special indeed:

The total sum of the distances between every pair

must be minimized to keep clean the air.

But if $$$x_i$$$ is zero and there is no objection,

we'd like you to answer the following question:

If you were to match everything now in the way you've been told

How many pairs would cross this given road?

**This problem has the same idea, data, and samples (but different flavor-text) as another problem written for a training camp by Travis Meade, and tested by myself. Seems to me to be a notorious coincidence. :)

Input

The first line will contain a single integer $$$c$$$: the number of test cases.

For each testcase, the first line contains $$$n$$$ and $$$q$$$: the number nodes in Thneedville, and the number of queries. $$$n-1$$$ lines follow, each containing a pair of integers describing the edges in Thneedville.

$$$q$$$ lines follow, each of the form $$$a$$$ $$$b$$$ $$$x_i$$$ . If $$$x_i$$$ is zero, we are asking about the number of matched pairs that cross the edge from $$$a$$$ to $$$b$$$ (there will always be an edge directly connecting $$$a$$$ to $$$b$$$). Otherwise, it indicates that we have created $$$x_i$$$ seeds at node $$$a$$$, and $$$x_i$$$ pots at node $$$b$$$.

$$$c \leq 20$$$

$$$1 \leq n, q \leq 10^5$$$

$$$1 \leq a, b \leq n$$$

$$$0 \leq x_i \leq 10^8$$$

Output

For each query in which $$$x_i$$$ is zero, print a single integer: the number of pairs crossing the queried edge.

Example
Input
2
6 5
1 2
2 3
3 4
4 5
4 6
1 6 2
2 5 3
4 3 0
6 2 2
4 3 0
4 6
1 2
1 3
4 1
1 2 0
3 4 5
4 2 1
1 3 0
1 4 0
1 2 0
Output
5
3
0
5
4
1