Звіт енергії блискавки
У місті Грім знаходиться багато будинків, і всі вони працюють від блискавок. Два будинки можуть бути з'єднані між собою дротом. Дріт сполучає будинки таким чином, що завжди існує лише один шлях з одного будинку до іншого. Кожен будинок має велику батарею, яка може зберігати нескінченну кількість електричної енергії.
Кожен день кілька блискавок влучають у деякі будинки. Ці блискавки досить незвичайні. При ударі блискавка одночасно потрапляє в два будинки: в один будинок (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 наприкінці кожного місяця.