The city of Thunder has many houses and they are powered by lightning. Two houses may be interconnected by a wire. The wires connect the houses such that there is exactly one path from one house to any other house in the city. Each house has a large battery that can store infinite electrical energy. Everyday, several lightnings strike several houses. These lightnings are very unusual, when it strikes, it strikes two houses simultaneously: one house (\textbf{A}) with a red lightning and the other house (\textbf{B}) with a blue lightning. After the strikes, every house along the path from \textbf{A} to \textbf{B} (inclusive) will receive a certain amount of electrical energy which is then added to the house's battery. The mayor of Thunder city wants a report on the stored electrical energy for every house at the end of the month and the owner of each house has to pay taxes for that. To prevent the owners report invalid energy stored in their house battery (because they want less tax to pay), you are asked to produce a correct report based on the observed lightnings of the current month. At the beginning of the month, the energy reading on the battery of each house is \textbf{0}. \InputFile The first line of input contains an integer \textbf{T} (\textbf{T}\textit{ ≤} \textbf{10}), the number of cases. Each case begins with an integer \textbf{N} (\textbf{2}\textit{ ≤ }\textbf{N}\textit{ ≤ }\textbf{50, 000}), the number of houses in the Thunder city. The next \textbf{N - 1} lines contain the wire connections where each line will consist of two integers \textbf{X} and \textbf{Y} which means house \textbf{X} is connected with house \textbf{Y}. The house number is from \textbf{0} to \textbf{N - 1}. The next line will contain a number \textbf{Q} (\textbf{1}\textit{ ≤ }\textbf{Q}\textit{ ≤ }\textbf{50, 000}) which denotes the number of observed lightning strikes. The next \textbf{Q} lines describe the unusual lightnings happened during the month. Each line will consist of three integers \textbf{ A}, \textbf{B}, \textbf{C} which tells that a red lightning strikes house \textbf{A} and a blue lightning strikes house \textbf{B} and the power transferred is \textbf{C} (at most \textbf{100}) based on the reading of a special lightning instrument. \OutputFile For each case, output "\textbf{Case #X:}" (without quote) where \textbf{X} is the case number and \textbf{N} lines where each line is the electrical energy reading on the battery of each house from house \textbf{0} to house \textbf{N - 1} at the end of the month.