У Васи есть дерево из \(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\) чисел. \(i\)-е число должно равняться значению, записанному в \(i\)-й вершине после обработки всех запросов.
Примечание
В первом тестовом примере изначально значения в вершинах равны \(0, 0, 0, 0, 0\). После первого запроса значения будут равны \(1, 1, 1, 0, 0\). После второго запроса значения будут равны \(1, 11, 1, 0, 0\). После третьего запроса значения будут равны \(1, 11, 1, 100, 0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2
1 3
2 4
2 5
3
1 1 1
2 0 10
4 10 100
|
1 11 1 100 0
|
|
2
|
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
|