Дано дерево на n вершинах (пронумерованных от 1 до n) с корнем в вершине 1. В вершине i записаны два числа: ai и bi.
Вы можете прыгнуть из вершины в любую вершину в её поддереве. Стоимость такого прыжка из вершины x в вершину y равна произведению ax и by. Суммарная стоимость пути между вершинами, состоящего из нескольких прыжков равна сумме стоимостей прыжков в нём. Для каждой вершины посчитайте минимальную стоимость пути от неё до какого-либо листа. Обратите внимание, что корень дерева не является листом, даже если имеет степень 1.
Учтите, что нельзя совершать прыжок из вершины в ту же вершину.
Выходные данные
Выведите n целых чисел через пробел, i-е из которых обозначает минимальную стоимость, чтобы добраться от вершины с номером i до какого-либо листа.
Примечание
В первом тестовом примере вершина 3 сама является листом, поэтому ответ равен 0. Для вершины 2 прыжок в вершину 3 стоит a2 × b3 = 50. Для вершины 1 прыжок в вершину 3 стоит a1 × b3 = 10.
Во втором тестовом примере вершины 3 и 4 являются листьями, поэтому ответ для них равен 0. Для вершины 2 прыжок в вершину 4 стоит a2 × b4 = 100. Для вершины 1 необходимо сначала прыгнуть в вершину 2 прыжком стоимостью a1 × b2 = - 400, а затем прыгнуть из 2 в 4 за a2 × b4 = 100.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 10 -1
7 -7 5
2 3
2 1
|
10 50 0
|
|
2
|
4
5 -10 5 7
-8 -80 -3 -10
2 1
2 4
1 3
|
-300 100 0 0
|