ami có một cây \(n\) đỉnh, các đỉnh được đánh số từ \(1\) đến \(n\), và ở đỉnh \(i\) chứa một số \(a_i\). Gọi \(gcd(u,v)\) là ước chung lớn nhất của tất cả các đỉnh trong đường đi từ \(u\) đến \(v\). Đường đi ở đây chỉ đi qua các đỉnh và cạnh đúng 1 lần (đường đi ngắn nhất). Gọi \(dist(u, v)\) là số đỉnh trên đường đi từ \(u\) đến \(v\). Hãy tìm 2 đỉnh \(u\) và \(v\) mà \(gcd(u,v) > 1\) và \(dist(u,v)\) đạt max.

Input

• Dòng đầu tiên chứa một số nguyên dương \(n\) là số đỉnh của cây.
• Dòng tiếp theo chứa \(n\) số nguyên dương \(a_i\) là số ở đỉnh \(i\).
• \(n-1\) dòng tiếp theo, mỗi dòng chứa 2 số \(u\) và \(v\) là một cạnh của cây.

Output

• Một dòng là đáp án.

Example

5
1 2 2 4 5
1 2
2 3
3 4
4 5

3

Giới hạn

• \(2 \leq n \leq 2 \cdot 10^5\)
• \(1 \leq a_i \leq 2 \cdot 10^5\)