У Алёны есть дерево из n вершин. Корень дерева — вершина с номером 1. В вершину с номером i Алёна записала положительное целое число ai. Также, девочка записала на каждом ребре дерева какое-то положительное целое число (возможно, различные числа на различных ребрах).
Определим dist(v, u) как сумму чисел, записанных на ребрах, которые лежат на кратчайшем пути из v в u.
Вершина дерева v контролирует вершину u (v ≠ u), если u лежит в поддереве v и dist(v, u) ≤ au.
Девочка хочет поселиться в некоторой вершине дерева. Для этого она хотела бы знать для каждой вершины v, сколько в дереве есть вершин u таких, что вершина v контролирует вершину u.
Выходные данные
Выведите в одной строке n чисел — i-е из этих чисел должно равняться количеству вершин, которое контролируется вершиной с номером i.
Примечание
В тесте из условия вершина 1 контролирует вершину 3, также вершина 3 контролирует вершину 5 (обратите внимание, отсюда не следует, что вершина 1 контролирует вершину 5).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 5 1 4 6
1 7
1 1
3 5
3 6
|
1 0 1 0 0
|
|
2
|
5
9 7 8 6 5
1 1
2 1
3 1
4 1
|
4 3 2 1 0
|