«Он разбойник, и он знаменит, Храбрый Andrii Popa.

Днём и ночью он скачет верхом, Собирает дань на большой дороге, И повсюду в стране Ловцы воров убегают со всех ног»

— «Andrii Popa», Phoenix

У Ghiță есть индексируемая с $0$ последовательность $S$ из $N$ положительных целых весов. Поскольку он король Карпат, он хочет построить двоичное дерево, вершины которого имеют индексы $0, 1, \ldots, N - 1$, такое что:

• Симметричный (центрированный, inorder) обход дерева выдаёт вершины в порядке возрастания индексов. Симметричный обход двоичного дерева состоит из симметричного обхода поддерева с корнем в левом сыне корня (если такой сын существует), за которым следует индекс корня, а затем — симметричный обход поддерева с корнем в правом сыне корня (если такой сын существует).
• Если вершина $x$ является родителем вершины $y$, то $S_x$ делит $S_y$.

Напомним, что двоичное дерево — это древовидная структура данных, в которой каждая вершина имеет не более двух сыновей, называемых левым сыном и правым сыном.

К несчастью, знаменитый разбойник Andrii Popa украл последовательность $S$, и Ghiță больше не может обращаться к ней напрямую. Используя передовые технологии (свой мобильный телефон), он может для любых двух непрерывных подпоследовательностей $[a, b]$ и $[c, d]$ последовательности $S$ узнать, верно ли, что $\gcd[a, b]$ равен $\gcd[c, d]$, где $\gcd[x, y]$ — наибольший общий делитель чисел $S_x, S_{x+1}, S_{x+2}, \ldots, S_y$. К сожалению, эта технология довольно дорога: если Ghiță воспользуется ею более $Q$ раз, ему придётся заплатить крупный штраф. Помогите ему построить требуемое дерево, использовав эту технологию не более $Q$ раз. Гарантируется, что это возможно. Любое корректное решение будет принято.

Протокол взаимодействия

Участнику следует подключить заголовочный файл popa.h (C / C++) или реализовать модуль popa.pas (Pascal). Участнику необходимо реализовать следующую функцию:

int solve(int N, int* Left, int* Right);

function solve(N: LongInt, var Left, Right: array of LongInt): LongInt;

Эта функция должна вернуть корень дерева и записать в $\text{Left}_i$ и $\text{Right}_i$ соответственно левого и правого сына вершины $i$. Если у вершины $i$ нет левого сына, то $\text{Left}_i$ должно быть равно $-1$. Если у вершины $i$ нет правого сына, то $\text{Right}_i$ должно быть равно $-1$. Указатели Left и Right указывают на два уже выделенных массива размера ровно $N$.

Функция solve может быть вызвана не более $5$ раз в течение одного запуска. Рекомендуем соблюдать осторожность при использовании глобальных переменных.

Участник может вызывать следующую функцию:

int query(int a, int b, int c, int d);

function query(a, b, c, d: LongInt): LongInt;

Эта функция возвращает $1$ тогда и только тогда, когда $\gcd[a, b]$ равен $\gcd[c, d]$, где $0 \le a \le b < N$ и $0 \le c \le d < N$, и $0$ в противном случае.

Подзадачи

Подзадача 1 (37 баллов)

• $N = 100$
• $Q = 10000$

Подзадача 2 (24 балла)

• $N = 1000$
• $Q = 20000$

Подзадача 3 (39 баллов)

• $N = 1000$
• $Q = 2000$

Примеры

Пример взаимодействия для $S = [12, 4, 16, 2, 2, 20]$:

Примечание

Пример дерева такого вида, который хочет получить Ghiță для приведённого выше примера: