Cây GCD

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

Scoring

\(2 \leq n \leq 2*10^5\).

\(1 \leq a_i \leq 2*10^5\)