Problem Description

You are given a tree (an acyclic undirected connected graph) with N nodes. The tree nodes are numbered from 1 to N



There are N - 1 edges numbered from 1 to N - 1.



Each node has a value and each edge has a value. The initial value is 0.



There are two kind of operation as follows:



● ADD1 u v k: for nodes on the path from u to v, the value of these nodes increase by k.



● ADD2 u v k: for edges on the path from u to v, the value of these edges increase by k.



After finished M operation on the tree, please output the value of each node and edge.

 

Input

The first line of the input is T (1 ≤ T ≤ 20), which stands for the number of test cases you need to solve.



The first line of each case contains two integers N ,M (1 ≤ N, M ≤10⁵),denoting the number of nodes and operations, respectively.



The next N - 1 lines, each lines contains two integers u, v(1 ≤ u, v ≤ N ), denote there is an edge between u,v and its initial value is 0.



For the next M line, contain instructions “ADD1 u v k” or “ADD2 u v k”. (1 ≤ u, v ≤ N, -10⁵ ≤ k ≤ 10⁵)

 

Output

For each test case, print a line “Case #t:”(without quotes, t means the index of the test case) at the beginning.



The second line contains N integer which means the value of each node.



The third line contains N - 1 integer which means the value of each edge according to the input order.

 

Sample Input

2

4 2

1 2

2 3

2 4

ADD1 1 4 1

ADD2 3 4 2

4 2

1 2

2 3

1 4

ADD1 1 4 5

ADD2 3 2 4

 

Sample Output

Case #1:

1 1 0 1

0 2 2

Case #2:

5 0 0 5

0 4 0

 

Source

2014 ACM/ICPC Asia Regional Shanghai Online