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$