【题目背景】

一次模拟赛爆零的失意怎能难倒我们的 $\text{goodier}$？又怎会磨灭他的信心和执着？

是的，喜好与兴趣之所以珍贵，从不是因为我们与所好有多么优秀，而是说不管它们是否完美，不管自己能否成功，我们都对来路无怨无悔。

也正因如此，$\text{goodier}$ 清楚，其实早在他真正决定出发之时，这段时光中最坎坷的旅程便已结束了。

于是你看，摆在眼前的路是那样的清晰明朗呀——走下去，为 $\text{goodier}$ 加油鼓气，助他重振旗鼓，再铸辉煌！

——让那些前途与命运都随风去吧，我们活在当下。

【题目描述】

$\text{goodier}$ 一共有 $n$ 个好朋友，每个好朋友都有一个自己最喜欢的数字 $a_i$，他们将站成一颗树的模样为 $\text{goodier}$ 鼓气。

由于 $\text{goodier}$ 非常热衷于 $\gcd$ 运算，所以他的好朋友们为了让加油的效果最好，决定让他们最喜欢的数字的 $\gcd$ 最大（即使得 $\gcd(a_1, a_2 \dots a_n)$ 最大）。

但是他的好朋友们都各有自己喜欢的数字，所以在他们商量后，决定将一串挨着的好朋友各自把自己喜欢的数字加上一个 $k$（$k \leq 10^{18}$），使得最后的 $\gcd$ 值最大。

具体地说，题目给定一棵 $n$ 个点的带点权树，你需要任选三个数 $u, v, k$， 满足 $1 \leq u, v \leq n, 0 \leq k \leq 10^{18}$，将树上结点 $u$ 到结点 $v$ 的路径上每一个结点 $i$（包含结点 $u$ 和结点 $v$）的点权 $a_i$ 加上 $k$，使得 $\gcd(a_1, a_2 \dots a_n)$ 最大。

【输入格式】

从 cheer.in 中读入数据。

第一行两个整数，表示好朋友的数量 $n$ 和子任务的编号 $id$（在样例中 $id=0$）。

第二行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个好朋友喜欢的数字 $a_i$。

接下来 $n - 1$ 行，每行两个整数 $u, v$，表示好朋友 $u$ 和好朋友 $v$ 互相挨着。

【输出格式】

将答案输出到 cheer.out 中。

第一行一个整数，表示进行一次操作后最大的 $\gcd(a_1, a_2 \dots a_n)$。

第二行输出选择的 $u, v, k$（用空格分隔），如果有多种符合条件的方案，则任意选择一种输出，要求 $k \leq 10^{18}$。

【样例1输入】

8 0
1 4 2 6 3 1 2 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8

【样例1输出】

1
1 4 263121

【样例2输入】

5 0
4 4 7 3 4
1 2
2 5
1 3
3 4

【样例2输出】

4
3 4 263121

【子任务】

对于 $100\%$ 的数据，$1\leq n \leq 5 \times 10^5, 0\leq a_i \leq 10^{15}$。

上表“树的形态”一栏中，$\texttt{A}$ 代表树的形态是一条链，$\texttt{B}$ 代表无特殊限制。

上表“特殊性质”一栏中，$\texttt{A}$ 代表 $\max a_i \leq 10^6$，$\texttt{B}$ 代表 $n,a_i$ 均在数据范围内随机生成，$\texttt{C}$ 代表无特殊限制。