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 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.

给出一棵生成树，每个节点都有一个值，现在要求出每个节点的美丽值的最大值，美丽值的定义为从根节点到该节点(包含)路径上所有点的值的gcd，求解每个 点时可以把路径上某一个点的值变为0（就相当于删除这个节点的数）。你可以认为每个点美丽值的求解是独立的（每次删除的点都不会影响下一次）。

First line contains one integer number n — the number of vertices in tree (1 ≤ n ≤ 2·10⁵).

Next line contains n integer numbers a_i (1 ≤ i ≤ n, 1 ≤ a_i ≤ 2·10⁵).

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 n numbers separated by spaces, where i-th number equals to maximum possible beauty of vertex i.

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<set>

 using namespace std;

 struct Node

 {

   int next,to;

 }edge[];

 int num,head[],c[],a[],n;

 set<int>Set[];

 void add(int u,int v)

 {

   num++;

   edge[num].next=head[u];

   head[u]=num;

   edge[num].to=v;

 }

 int gcd(int a,int b)

 {

   if (!b) return a;

   return gcd(b,a%b);

 }

 void dfs(int x,int pa)

 {

   for (int i=head[x];i;i=edge[i].next)

     {

       int v=edge[i].to;

       if (v==pa) continue;

       c[v]=gcd(c[x],a[v]);

       Set[v].insert(c[x]);

       for (set<int>::iterator i=Set[x].begin();i!=Set[x].end();i++)

     Set[v].insert(gcd(a[v],*i));

       dfs(v,x);

     }

 }

 int main()

 {int i,u,v;

   cin>>n;

   for (i=;i<=n;i++)

     {

       scanf("%d",&a[i]);

     }

   for (i=;i<=n-;i++)

     {

       scanf("%d%d",&u,&v);

       add(u,v);add(v,u);

     }

   c[]=a[];

   Set[].insert();

   dfs(,);

   cout<<a[]<<' ';

   for (i=;i<n;i++)

     printf("%d ",*(--Set[i].end()));

   if (n>)

   cout<<*(--Set[n].end())<<endl;

 }