F. Сбежать через лист
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево на n вершинах (пронумерованных от 1 до n) с корнем в вершине 1. В вершине i записаны два числа: ai и bi.

Вы можете прыгнуть из вершины в любую вершину в её поддереве. Стоимость такого прыжка из вершины x в вершину y равна произведению ax и by. Суммарная стоимость пути между вершинами, состоящего из нескольких прыжков равна сумме стоимостей прыжков в нём. Для каждой вершины посчитайте минимальную стоимость пути от неё до какого-либо листа. Обратите внимание, что корень дерева не является листом, даже если имеет степень 1.

Учтите, что нельзя совершать прыжок из вершины в ту же вершину.

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

В первой строке содержится целое число n (2 ≤ n ≤ 105) — количество вершин в дереве.

Во второй строке через пробел заданы n целых чисел a1,  a2,  ...,  an( - 105  ≤  ai  ≤  105).

Во третьей строке через пробел заданы n целых чисел b1,  b2,  ...,  bn( - 105  ≤  bi  ≤  105).

В следующих n  -  1 строках содержатся пары целых чисел ui и vi (1 ≤ ui,  vi ≤  n), разделённых пробелом, обозначающие ребро между вершинами ui и vi в дереве.

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

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

Примеры
Входные данные
3
2 10 -1
7 -7 5
2 3
2 1
Выходные данные
10 50 0
Входные данные
4
5 -10 5 7
-8 -80 -3 -10
2 1
2 4
1 3
Выходные данные
-300 100 0 0
Примечание

В первом тестовом примере вершина 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.