«Він розбійник і він славетний, Хоробрий 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ță для попереднього прикладу: