The Shortest Problem

Hooray! You have came to the right problem! This problem has the shortest description... at least in this contest :-)

In this task, you are given an undirected unrooted tree of N vertices and Q queries; you should process all queries one by one.

There are two types of query:

• u A B K  : add all vertices' value that lie in the path from node A to B, inclusive, by K (could be negative).
• q        : output the highest value of any vertex in the entire tree at that moment.

Input

The first line of input contains an integer T (1 ≤ T ≤ 100) the number of cases. Each case begins with two integers N and Q (1 ≤ N ≤ 20,000; 1 ≤ Q ≤ 5,000) denoting the number of vertices in the tree and the number of queries respectively. The vertices are numbered from 1..N. The next N-1 lines each contains two integers a_i and b_i (1 ≤ a_i, b_i ≤ N; a ≠ b) representing an edge connecting vertex a_i and vertex b_i. The next Q lines contains one of the two following format:

1. u a_i b_i k_i (1 ≤ a_i, b_i ≤ N; -1,000 ≤ k_i ≤ 1,000) .
2. q

Warning: This problem has a large input file.

Output

For each case, output in a line "Case #X:" where X is the case number starts from 1. For each q query in the input, output in a line the highest value in any vertex in the tree at that moment.

2
5 7
1 2
2 3
3 4
2 5
u 1 3 2
u 5 4 3
q
u 2 3 -4
q
u 1 1 10
q
3 5
1 2
2 3
q
u 1 2 -5
q
u 2 3 -6
q

Case #1:
5
3
12
Case #2:
0
0
-5

Explanation for the 1^st sample input.

The initial condition:

After the first update (u 1 3 2):

After the second update (u 5 4 3):

q query on this tree will output 5 (node 2 and node 3 have such value).

After the third update (u 2 3 -4):

q query on this tree will output 3 (node 4 and node 5 have such value).

After the fourth update (u 1 1 10):

q query on this tree will output 12 (node 1 has such value).