Cặp lớn nhất

Cho một cây gồm $n$ đỉnh. Mỗi cạnh có một trọng số và mỗi đỉnh có một nhãn. Ký hiệu nhãn của đỉnh $i$ là $\text{label}(i)$.

Một đường đi đơn từ đỉnh $s$ đến đỉnh $t$ là một dãy đỉnh có thứ tự $v_0\to v_1\to v_2\to \dots \to v_k$, trong đó $v_0=s$, $v_k=t$ và các $v_i$ đôi một khác nhau. Với mọi chỉ số $i$ hợp lệ, $v_i$ và $v_{i+1}$ được nối trực tiếp bởi một cạnh. Lưu ý rằng trong một cây luôn có đường đi đơn giữa mọi cặp đỉnh.

Ta định nghĩa:

• $\text{dist}(u,v)$ là tổng trọng số các cạnh trên đường đi đơn từ $u$ đến $v$;
• $\text{greatness}(u,v)=\text{dist}(u,v)·gcd(\text{label}(u),\text{label}(v))$.

Hãy tìm hai đỉnh khác nhau $u$ và $v$ có $\text{greatness}(u,v)$ lớn nhất.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ dữ liệu, mỗi bộ dữ liệu có dạng:

• Dòng đầu tiên chứa một số nguyên $n$ ($2\le n\le {10}^5$).
• Dòng thứ hai chứa $n$ số nguyên, số thứ $i$ là $\text{label}(i)$ ($1\le \text{label}(i)\le 5·{10}^5$).
• $n-1$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u$, $v$, $w$ ($1\le u,v\le n$, $1\le w\le {10}^6$) mô tả một cạnh trọng số $w$ nối hai đỉnh $u$ và $v$.

Dữ liệu vào kết thúc bằng một dòng chứa số $0$, dòng này không phải là một bộ dữ liệu.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng chứa giá trị lớn nhất của $\text{greatness}(u,v)$.

Ràng buộc

• $2\le n\le {10}^5$, tổng $n$ qua tất cả các bộ dữ liệu không vượt quá ${10}^5$.
• $1\le \text{label}(i)\le 5·{10}^5$, $1\le w\le {10}^6$.

Ví dụ