Отчет энергии молнии
В городе Гром находится много домов, и все они работают на молнии. Два дома могут быть соединены между собой проводом. Провода соединяют дома таким образом, что всегда имеется только один путь из одного дома в другой. Каждый дом имеет большую батарею, которая может хранить бесконечное количество электрической энергии.
Каждый день несколько молний ударяют в некоторые дома. Эти молнии достаточно необыкновенные. При ударе молния одновременно попадает в два дома: в один дом (A) попадает красная молния, а в другой дом (B) синяя молния. После удара каждый дом на пути от A до B (включительно) получает некоторое количество электрической энергии, которая добавляется к батарее дома.
Мэр города Гром хочет получить отчет о хранящейся электрической энергии в каждом доме в конце месяца, так как владелец каждого дома должен заплатить за полученную энергию налоги. Чтобы не допустить владельцам сообщать неправильные данные об энергии, запасенной в батарее их дома (так как жители хотят платить меньше налогов), Вас просят составить правильный отчет на основе наблюдения за молниями на протяжении месяца. В начале месяца энергия на батарее каждого дома равнялась 0.
Входные данные
Первая строка содержит количество тестов T (T ≤ 10). Каждый тест начинается целым числом N (2 ≤ N ≤ 50, 000) - количеством домов в городе Гром. Следующие N - 1 строк содержат информацию о соединении домов проводами: каждая строка содержит два целых числа X и Y, обозначающих, что дом X соединен с домом Y. Дома пронумерованы числами от 0 до N - 1. Следующая строка содержит количество ударов молнии Q (1 ≤ Q ≤ 50, 000). Следующие Q строк описывают необычные удары молнии, которые имеют место каждый месяц. Каждая строка содержит три целых числа A, B, C, означающих, что красная молния попадает в дом A, синяя молния в дом B, передаваемая мощность энергии равна C (не более 100), которая вычисляется специальными приборами.
Выходные данные
Для каждого теста вывести "Case #X:" (без кавычек), где X означает номер теста, а также N строк, описывающих электрическую энергию батарей всех домов от номера 0 до N - 1 в конце каждого месяца.