A far away galaxy, H10 has newly been discovered and incorporated into the Commonwealth which participates in the Galactic Wars. The other galaxies have always bullied it by winning the Galactic Wars every year. Frustrated, H10 has come up with a novel strategy to distract the other galaxies. They are planning to send beautiful nymphs into the lands of the other galaxies.

The cosmos is arranged so that there is a unique path between any two galaxies (possibly going through other galaxies). The leaders in H10 will select two different galaxies A and B, and send K nymphs to each of the galaxies that is on the unique path from A to B. Initially there are no nymphs on any galaxy.

You are the Chief Executive Officer of this project. The leaders will ask you to send these groups of nymphs by giving various instructions of the form (A, B, K). In the process, they may also ask you how many nymphs are currently there in particular galaxies, so that they are able to take smart decisions in the future. Implement this. (See exact format in Input/Output Specifications)

Input

The first line contains t, the number of test cases.

T test cases follow. Each contains:

A line containing n, the number of galaxies (numbered from 0 to n-1).

n-1 lines describing the connections between 2 galaxies as 2 space separated integers a, b (both from 0 to n-1), denoting a direct connection between galaxy a, and galaxy b.

The next line contains a single integer Q denoting the number of queries.

Next Q lines contain queries in the form of 3 space separated integers a, b and k.

Output

For each query if k ≥ 0, don't output anything, just send the nymphs to every galaxy on the way.

In a query if k = -1, then output 2 space separated integers in a new line denoting the number of nymphs in galaxy a, and galaxy b respectively.

Constraints

1 ≤ T ≤ 10

2 ≤ n ≤ 50,000

The galaxies are connected in such a way that there is a unique path from each galaxy to every other galaxy.

2 ≤ Q ≤ 50,000

0 ≤ a, b ≤ n-1

a and b are different.

-1 ≤ k ≤ 100

Example

Input:
1
3
0 1
1 2
2
1 2 2
0 2 -1

Output:
0 2

Explanation

The path from 1 to 2 is 1 → 2. 2 nymphs are thus sent to galaxies 1 and 2. There were 0 nymphs at galaxy 0 initially.