\begin{tutorial}{НСД, Сума, Помножити. що?...}

Перший важливий факт для розв'язання цієї задачі --- $\operatorname{gcd}$ змінюється не більше, ніж $\log A$ разів. Це можна просто показати, нехай в нас $g_1, g_2$, де $g_2 = gcd(g_1, x)$. Тепер, якщо $g_1 \neq g_2$, то $\frac{g_1}{g_2} > 1$ (бо $g_2$ ділить $g_1$), тобто хоча б $2$, що значить, що кожен раз коли $\operatorname{gcd}$ змінюється, воно зменшується хоча б вдвічі.

Тепер, давайте для кожної позиції $i$ знайдемо позиції $j$ зліва і $k$ справа, де $\operatorname{gcd}$ змінюється. Але, треба запам'ятати для кожного $\operatorname{gcd}$ останню позицію, так, щоб довжина відрізка [$j;i$] чи [$i;k$] була максимальною. Для кожної позиції в нас є $\mathcal{O}(\log A)$ позицій, де $\operatorname{gcd}$ змінюється.

Зафіксуймо праву границю $r$, тоді щоб відповідати на запити підтримуймо масив $b$, що $b_i$ --- найбільша відповідь для відрізків, що мають ліву границю в $i$, і їх права границю менше рівна $r$.

Щоб відповісти на запит $[l;r]$ питаємо максимум в масиві $b$ на відрізку $[l;r]$ і треба перевірити всі відрізки, які починались в цьому відрізку, але закінчились лівіше. Тоді $a_l$ точно було взято у відрізок, то перевіримо всі відрізки, де змінюється $\operatorname{gcd}$ справа від $l$.

Таке можна розв'язувати офлайн за допомогою дерева відрізків і сортуванням запитів, чи онлайн, за допомогою персистентного дерева відрізків.

Розв'язок з персистентним деревом відрізків має асимптотику $\mathcal{O}(N \log N \log N + Q \cdot (\log A + \log N))$. Інші розв'язки, які відомі мені, мають таку саму асимптотику, але кращу константу, що робить їх значно швидшими.

\textit{На початку планувалось зробити всі запити онлайн щоб було цікавіше розв'язувати задачу, але через деякі причини було вирішено зробити задачу стандартною --- хто хоче розв'язувати офлайн --- нехай розв'язує}

Автор усіх задач: Андрій Столітній

\end{tutorial}
