Илья очень любит графы, особенно деревья. Во время последнего похода в лес Илья нашел очень интересное дерево с корнем в вершине 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
| Codeforces Round 430 (Div. 2) |
|---|
| Закончено |
