Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Ilya And The Tree

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIlya is very fond of graphs, especially trees. During his last trip to the forest Ilya found a very interesting tree rooted at vertex 1. There is an integer number written on each vertex of the tree; the number written on vertex *i* is equal to *a*_{i}.

Ilya believes that the beauty of the vertex *x* is the greatest common divisor of all numbers written on the vertices on the path from the root to *x*, including this vertex itself. In addition, Ilya can change the number in one arbitrary vertex to 0 or leave all vertices unchanged. Now for each vertex Ilya wants to know the maximum possible beauty it can have.

For each vertex the answer must be considered independently.

The beauty of the root equals to number written on it.

Input

First line contains one integer number *n* — the number of vertices in tree (1 ≤ *n* ≤ 2·10^{5}).

Next line contains *n* integer numbers *a*_{i} (1 ≤ *i* ≤ *n*, 1 ≤ *a*_{i} ≤ 2·10^{5}).

Each of next *n* - 1 lines contains two integer numbers *x* and *y* (1 ≤ *x*, *y* ≤ *n*, *x* ≠ *y*), which means that there is an edge (*x*, *y*) in the tree.

Output

Output *n* numbers separated by spaces, where *i*-th number equals to maximum possible beauty of vertex *i*.

Examples

Input

2

6 2

1 2

Output

6 6

Input

3

6 2 3

1 2

1 3

Output

6 6 6

Input

1

10

Output

10

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/25/2018 05:18:30 (d3).

Desktop version, switch to mobile version.

User lists

Name |
---|