【题目背景】
一次模拟赛爆零的失意怎能难倒我们的 $\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}$。
| 子任务 | 分值 | $n$ | 树的形态 | 特殊性质 |
|---|---|---|---|---|
| 1 | 5 | $≤ 20$ | B | A |
| 2 | 10 | $≤ 2000$ | B | A |
| 3 | 5 | $≤ 5 × 10^4$ | A | A |
| 4 | 5 | $≤ 5 × 10^4$ | B | A |
| 5 | 10 | $≤ 5 × 10^5$ | A | A |
| 6 | 5 | $≤ 5 × 10^5$ | B | B |
| 7 | 20 | $≤ 5 × 10^5$ | A | B |
| 8 | 40 | $≤ 5 × 10^5$ | B | C |
上表“树的形态”一栏中，$\texttt{A}$ 代表树的形态是一条链，$\texttt{B}$ 代表无特殊限制。
上表“特殊性质”一栏中，$\texttt{A}$ 代表 $\max a_i \leq 10^6$，$\texttt{B}$ 代表 $n,a_i$ 均在数据范围内随机生成，$\texttt{C}$ 代表无特殊限制。