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 \)