Lightning Energy Report

The city of Thunder is a network of houses that run on lightning. Some pairs of houses are joined by wires, and the wires form a tree: between any two houses there is exactly one path. Every house has a battery that can hold an unlimited amount of energy, and at the start of the month every battery reads $0$.

During the month, lightning strikes the city many times. Each strike is unusual: it hits two houses at the same instant — house $A$ with a red bolt and house $B$ with a blue bolt — and delivers $C$ units of energy to every house on the path from $A$ to $B$ (both endpoints included). That energy is added to each of those houses' batteries.

At the end of the month the mayor needs a report of the total energy stored in every house's battery. Produce that report from the month's observed strikes.

The first line contains an integer $T$ ($T \le 10$) — the number of test cases. Each test case is given as follows.

• A line with an integer $N$ ($2 \le N \le 50000$), the number of houses, numbered $0$ through $N-1$.
• $N-1$ lines, each with two integers $X$ and $Y$ ($0 \le X, Y \le N-1$), meaning houses $X$ and $Y$ are joined by a wire. These wires always form a tree.
• A line with an integer $Q$ ($1 \le Q \le 50000$), the number of strikes.
• $Q$ lines, each with three integers $A$, $B$, and $C$ ($0 \le A, B \le N-1$, $1 \le C \le 100$): a strike that adds $C$ units of energy to every house on the path from house $A$ to house $B$. $A$ and $B$ may be equal, in which case only that single house is charged.

For each test case, first print a line Case #X:, where $X$ is the test case number starting from $1$. Then print $N$ lines: the $i$-th line (for $i = 0, 1, \ldots, N-1$) is the total energy stored in the battery of house $i$ at the end of the month.