E. Вася и дерево
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Васи есть дерево из $$$n$$$ вершин с корнем в вершине $$$1$$$. Изначально в каждой вершине записано число $$$0$$$.

Определим $$$d(i, j)$$$ как расстояние между вершинами $$$i$$$ и $$$j$$$ в дереве, то есть количество ребер на кратчайшем пути из $$$i$$$ в $$$j$$$. Также определим поддерево глубины $$$k$$$ вершины $$$x$$$ — набор вершин $$$y$$$, таких, что выполняются следующие условия:

  • $$$x$$$ является предком $$$y$$$ (каждая вершина считается своим предком);
  • $$$d(x, y) \le k$$$.

Васе нужно обработать $$$m$$$ запросов к дереву. $$$i$$$-й запрос представляется тремя числами $$$v_i$$$, $$$d_i$$$ и $$$x_i$$$, и означает, что Васе нужно прибавить значение $$$x_i$$$ ко всем вершинам поддерева вершины $$$v_i$$$ на глубине $$$d_i$$$.

Сообщите Васе значение, записанное в каждой вершине после обработки всех запросов.

Входные данные

Первая строка содержит число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — количество вершин в дереве.

Следующие $$$n - 1$$$ строк содержат по два числа $$$x$$$ и $$$y$$$ ($$$1 \le x, y \le n$$$), представляющие ребро между вершинами $$$x$$$ и $$$y$$$. Гарантируется, что данные ребра составляют дерево.

Следующая строка содержит число $$$m$$$ ($$$1 \le m \le 3 \cdot 10^5$$$) — количество запросов.

Следующие $$$m$$$ строк содержат по три числа $$$v_i$$$, $$$d_i$$$, $$$x_i$$$ ($$$1 \le v_i \le n$$$, $$$0 \le d_i \le 10^9$$$, $$$1 \le x_i \le 10^9$$$) — описание $$$i$$$-го запроса.

Выходные данные

В единственной строке выведите $$$n$$$ чисел. $$$i$$$-е число должно равняться значению, записанному в $$$i$$$-й вершине после обработки всех запросов.

Примеры
Входные данные
5
1 2
1 3
2 4
2 5
3
1 1 1
2 0 10
4 10 100
Выходные данные
1 11 1 100 0
Входные данные
5
2 3
2 1
5 4
3 4
5
2 0 4
3 10 1
1 2 3
2 3 10
1 1 7
Выходные данные
10 24 14 11 11
Примечание

В первом тестовом примере изначально значения в вершинах равны $$$0, 0, 0, 0, 0$$$. После первого запроса значения будут равны $$$1, 1, 1, 0, 0$$$. После второго запроса значения будут равны $$$1, 11, 1, 0, 0$$$. После третьего запроса значения будут равны $$$1, 11, 1, 100, 0$$$.