{"raw_statement":[{"iden":"statement","content":"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_.\n\nIlya 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.\n\n_For each vertex the answer must be considered independently._\n\n_The beauty of the root equals to number written on it._"},{"iden":"input","content":"First line contains one integer number _n_ — the number of vertices in tree (1 ≤ _n_ ≤ 2·105).\n\nNext line contains _n_ integer numbers _a__i_ (1 ≤ _i_ ≤ _n_, 1 ≤ _a__i_ ≤ 2·105).\n\nEach 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."},{"iden":"output","content":"Output _n_ numbers separated by spaces, where _i_\\-th number equals to maximum possible beauty of vertex _i_."},{"iden":"examples","content":"Input\n\n2\n6 2\n1 2\n\nOutput\n\n6 6 \n\nInput\n\n3\n6 2 3\n1 2\n1 3\n\nOutput\n\n6 6 6 \n\nInput\n\n1\n10\n\nOutput\n\n10"}],"translated_statement":[{"iden":"statement","content":"Ilya 非常喜欢图，尤其是树。在他最近一次去森林的旅行中，Ilya 找到一棵以顶点 #cf_span[1] 为根的有趣树。树上的每个顶点上都写有一个整数，顶点 #cf_span[i] 上写的数是 #cf_span[ai]。\n\nIlya 认为顶点 #cf_span[x] 的美丽值是从根到 #cf_span[x] 的路径上所有顶点（包括 #cf_span[x] 自身）上所写数字的交错和。此外，Ilya 可以将任意一个顶点的数字改为 #cf_span[0]，或者保持所有顶点不变。现在，对于每个顶点，Ilya 想知道它所能达到的最大可能美丽值。\n\n_每个顶点的答案必须独立考虑。_\n\n_根的美丽值等于其上写的数字。_\n\n第一行包含一个整数 #cf_span[n] —— 树中顶点的数量（#cf_span[1 ≤ n ≤ 2·105]）。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[ai]（#cf_span[1 ≤ i ≤ n]，#cf_span[1 ≤ ai ≤ 2·105]）。\n\n接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[x] 和 #cf_span[y]（#cf_span[1 ≤ x, y ≤ n]，#cf_span[x ≠ y]），表示树中存在一条边 #cf_span[(x, y)]。\n\n请输出 #cf_span[n] 个用空格分隔的数，其中第 #cf_span[i] 个数等于顶点 #cf_span[i] 的最大可能美丽值。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n] —— 树中顶点的数量（#cf_span[1 ≤ n ≤ 2·105]）。第二行包含 #cf_span[n] 个整数 #cf_span[ai]（#cf_span[1 ≤ i ≤ n]，#cf_span[1 ≤ ai ≤ 2·105]）。接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[x] 和 #cf_span[y]（#cf_span[1 ≤ x, y ≤ n]，#cf_span[x ≠ y]），表示树中存在一条边 #cf_span[(x, y)]。"},{"iden":"output","content":"请输出 #cf_span[n] 个用空格分隔的数，其中第 #cf_span[i] 个数等于顶点 #cf_span[i] 的最大可能美丽值。"},{"iden":"examples","content":"输入\n2\n6 2\n1 2\n输出\n6 6\n\n输入\n3\n6 2 3\n1 2\n1 3\n输出\n6 6 6\n\n输入\n1\n10\n输出\n10"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of vertices in a rooted tree, with root at vertex $ 1 $.  \nLet $ a = (a_1, a_2, \\dots, a_n) \\in \\mathbb{Z}^n $ be the array of integers written on the vertices, where $ a_i $ is the value at vertex $ i $.  \nLet $ T = (V, E) $ be the tree with vertex set $ V = \\{1, 2, \\dots, n\\} $ and edge set $ E $ of size $ n-1 $, rooted at vertex $ 1 $.  \nFor each vertex $ x \\in V $, let $ P(x) $ denote the set of vertices on the unique path from the root $ 1 $ to $ x $, inclusive.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 2 \\cdot 10^5 $  \n2. $ 1 \\leq a_i \\leq 2 \\cdot 10^5 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. The graph is a tree.\n\n**Objective**  \nFor each vertex $ x \\in V $, define the *beauty* of $ x $ as:  \n$$\nb(x) = \\gcd\\left( \\{ a_v \\mid v \\in P(x) \\} \\right)\n$$  \nIlya may choose to set *at most one* vertex $ v \\in V $ to $ 0 $ (or leave all unchanged), and the beauty is then computed over the resulting values (with $ \\gcd(S \\cup \\{0\\}) = \\gcd(S) $ if $ S \\neq \\emptyset $, and $ \\gcd(\\{0\\}) = 0 $).\n\nFor each vertex $ x $, compute the **maximum possible beauty** over all choices of at most one vertex to set to $ 0 $, **considering each vertex independently**.\n\nThat is, for each $ x \\in V $, compute:  \n$$\n\\max_{S \\subseteq P(x),\\, |S| \\leq 1} \\gcd\\left( \\{ a_v \\mid v \\in P(x) \\setminus S \\} \\right)\n$$  \nwhere setting $ a_v = 0 $ for $ v \\in S $ is equivalent to excluding $ a_v $ from the GCD computation.\n\n**Note**: The GCD of an empty set is undefined, but since $ P(x) $ always contains the root, and we may remove at most one vertex, the set $ P(x) \\setminus S $ is never empty.","simple_statement":null,"has_page_source":false}