C. Илья и дерево
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Илья очень любит графы, особенно деревья. Во время последнего похода в лес Илья нашел очень интересное дерево с корнем в вершине 1, в каждой вершине i которого записано одно целое число ai.

Красотой вершины x Илья называет наибольший общий делитель всех чисел в вершинах на пути от корня до x включительно. При этом Илья может изменить число в одной произвольной вершине на 0, либо оставить все вершины неизменными. Теперь Илью интересует, какая максимальная красота может быть у каждой вершины.

Для каждой вершины ответ нужно считать независимо.

Красота корня равна числу, записанному на нем.

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

Первая строка содержит целое число n — количество вершин в дереве (1 ≤ n ≤ 2·105).

Следующая строка содержит n целых чисел ai (1 ≤ i ≤ n, 1 ≤ ai ≤ 2·105).

Каждая из следующий n - 1 строк содержит два целых числа x и y (1 ≤ x, y ≤ n, x ≠ y), означающие, что в дереве есть ребро (x, y).

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

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

Примеры
Входные данные
2
6 2
1 2
Выходные данные
6 6
Входные данные
3
6 2 3
1 2
1 3
Выходные данные
6 6 6
Входные данные
1
10
Выходные данные
10