B'Ilya 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 ai. 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. First line contains one integer number n -- the number of vertices in tree (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n xe2 x80 x89 xe2 x89 xa4 xe2 x80 x892 xc2 xb7105). Next line contains n integer numbers ai (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89i xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n, 1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89ai xe2 x80 x89 xe2 x89 xa4 xe2 x80 x892 xc2 xb7105). Each of next n xe2 x80 x89- xe2 x80 x891 lines contains two integer numbers x and y (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89x, xe2 x80 x89y xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n, x xe2 x80 x89 xe2 x89 xa0 xe2 x80 x89y), which means that there is an edge (x, xe2 x80 x89y) in the tree. Output n numbers separated by spaces, where i-th number equals to maximum possible beauty of vertex i. '...