P17897 [ICPC 2026 Nanchang I] Journey of GCD
Description
In the magical kingdom of Numerian, there are $n$ cities, each with its own magical power level $a_i$. The king has built bidirectional roads between every pair of cities. For the road connecting city $u$ and city $v$, its Guardian Charm Degree (GCD) equals $\gcd(a_u,a_v)$, which is the greatest common divisor of their magical power levels.
For a traveler moving from city $x$ to $y$, the Magical Immunity Number (MIN) of the journey is the minimum GCD among all roads taken. The royal advisors consider a journey “well-immune” if and only if its MIN is maximized.
You are tasked with answering $q$ queries from the king. For each query $(x,y)$, output the maximum possible MIN among all paths from city $x$ to city $y$.
In particular, if $x = y$, the traveler never leaves the city, so the MIN is simply the city's own magical power $a_x$.
Input Format
The first line contains two integers $n$ and $q$ ($1 \le n, q \le 10^6$).
The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le 10^6$), representing the magical power of each city.
Each of the next $q$ lines contains two integers $x$ and $y$ ($1 \le x, y \le n$), representing a query.
Output Format
For each query, output a single integer representing the maximum possible MIN.
Explanation/Hint
For the sample, the magical power levels are $a=[6,15,22,33,35,63]$.
Query 1: The optimal path is $5 \to 6$, and the answer is $\gcd(35,63)=7$.
Query 2: The optimal path is $3 \to 4 \to 6 \to 5$. The edge values are $\gcd(22,33)=11$, $\gcd(33,63)=3$, and $\gcd(63,35)=7$, so the answer is $\min(11,3,7)=3$.
Query 3: Since $x=y$, the traveler never leaves the city, so the answer is $a_2=15$.