You are given a directed graph with n nodes and m edges. The nodes are numbered from 1 to n, and node i is assigned a cost \(c_i\). The cost of a walk on the graph is defined as the greatest common divisor of the costs of the vertices used in the walk. Formally, the cost of a walk \(v_1, v_2, \cdots, v_k \) is given by \(\text{gcd} ( c_{v_1}, c_{v_2}, \cdots, c_{v_k} ) \). Note that \(v_i\)'s need not be distinct. Find the cost of the walk with minimum cost.

The walk might consist of single vertex.

Input

• The first line contains two integers, n, and m.
• The next line contains n space separated integers, \(i^{\text{th} } \) of which is equal to \(c_i\)
• Each of the next m lines contain two integers, u, and v, denoting a directed edge from u to v.

Output

• Print one integer containing the cost of the walk with minimum cost.

Constraints

• \(1 \le n, m, c_i \le 10^5 \)