НСД sorğuları

Giriş

Birinci sətir bir tam ədəd $n$ (2 \le n \le 2 \cdot 10^5 ) — massiv ölçüsünü göstərir.

İkinci sətir $n$ tam ədəd a_1, a_2, \ldots, a_n (1 \le a_i \le 10^6) — massiv elementlərini göstərir.

Üçüncü sətir bir tam ədəd $m$ (1 \le m \le 2 \cdot 10^5 ) — sorğuların sayını göstərir.

Növbəti $m$ sətirin hər biri iki tam ədəd l_i, r_i (1 \le l_i < r_i \le n) — sorğunun sərhədlərini göstərir.

Çıxış

Hər bir sorğu üçün bir tam ədəd çıxış edin — həmin sorğunun cavabı.

Nümunələr

Qeyd

\gcd(a, b)  — ədədlərin $a,b$ ən böyük ortaq bölənidir.

İkinci nümunəni nəzərdən keçirək:

• İlk dörd sorğuda seqment yalnız iki ədəddən ibarətdir, buna görə cavab onların ən böyük ortaq bölənidir.

• Sorğu $(1,5)$: ən böyük ortaq bölən a_1 və a_4 ədədlərindədir, \gcd(a_1, a_4)=\gcd(10, 50)=10.

• Sorğu $(3,5)$: \max(\gcd(a_3, a_4), \gcd(a_3, a_5), \gcd(a_4, a_5))=\max(2, 3, 1) = 3 hesablanmalıdır.

• Sorğu $(1,3)$: \max(\gcd(a_1, a_2), \gcd(a_1, a_3), \gcd(a_2, a_3))=\max(1, 2, 3) = 3 hesablanmalıdır.

Bal hesablama

1. ($12$ bal): m, n, a_i \leq 200;

2. ($7$ bal): m, n \leq 200;

3. ($17$ bal): a_i \leq 50;

4. ($7$ bal): bütün a_i — iki qüvvətləri;

5. ($27$ bal): m, n \leq 15000;

6. ($13$ bal): m, n \leq 35000;

7. ($17$ bal): əlavə məhdudiyyətlərsiz.