Given a tree with \(N\) vertices. Each vertex has a value \(a_i\). For vertex \(i\) and \(j\), if some vextex \(x\) is on the path between \(i\) and \(j\), and \(x\) is neither \(i\) nor \(j\), we update \(Ans_x=max(Ans_x,GCD(a_i,a_j))\). \(GCD\) means the greatest common divisor function. \(Ans\) is an array of \(N\) zeros initial.

Find the \(Ans\) array after all updation.

Input Format

First line contains an integer \(N(1\le N\le 10^5)\).

Second line contains \(N\) integers, represent the array \(a(1\le a_i\le 10^5)\).

Each of the next \(N-1\) lines contains two integers \(u,v\), represent an edge in the tree.

Output Format

\(N\) integers in one line, represent the array \(Ans\), separated by space.