Minimal Cost

You are given a set of cities( numbered from 1 to N ) that are connected with directed roads. Each city has a value assigned to it. Your task is to find a path such that minimizes the Great Common Devisor in the values of the cities on the path and output that minimum GCD value.

There can be a path that contains only one city.

Input Format

• The first line contains two integer N and M, number of cities and number of roads.
• Next line contains space seperated N integers represendting the value of the i^th (V_i) city.
• Each of the next M lines contain two integers S and E, denoting a directed road from city S to city E.

Output Format

Print the minimum GCD value you found.

Constraints

• 1 \(\leq\) N \(\leq\) 10⁵
• 1 \(\leq\) M \(\leq\) 10⁵
• 1 \(\leq\) V_i \(\leq\) 10⁵

Sample Input 0

3 2
4 6 8
1 2
2 3

Sample Output 0

2