Ця задача є інтерактивною.

На прилавку кондитерської «跳蚤» стоять два ряди різнобарвного двошарового желе (верхній шар — $a$, нижній — $b$). За правилом «взаємного доповнення під час застигання», що діє в крамниці, сума висот верхнього й нижнього шарів кожної порції желе дорівнює рівно $n+1$. Спочатку працівники впорядкували ці два ряди за висотою так, що кожен утворював ідеальну перестановку чисел $1 \sim n$, але минулої ночі жвавий працівник-блоха випадково поміняв місцями верхній і нижній шари желе в деяких позиціях!

Тепер щорічний фестиваль десертів ось-ось розпочнеться, і працівники мають відновити початкове розташування желе до перевертання (тобто послідовність висот верхнього шару $a$ до перевертання).

Ви не можете безпосередньо побачити висоту желе, але можете давати команди автоматичному вимірювальному приладу кондитерської: вказавши кілька позицій $i$, ви доручаєте приладу поміняти місцями верхній і нижній шари желе в цих позиціях. Прилад поверне різницю між найбільшою та найменшою висотами поточного верхнього шару (розмах), а також різницю між найбільшою та найменшою висотами нижнього шару (розмах). Увага: результат кожного перевертання зберігається.

Чи зможете ви за обмежену кількість перевертань із вимірюванням успішно відновити початкову послідовність розташування верхнього шару желе?

Спочатку бібліотека взаємодії вибирає перестановку $p$ чисел $1\sim n$ і будує перестановку $b_i=n+1-p_i$. Потім для кожного індексу $i$ бібліотека незалежно вирішує, чи міняти місцями два числа в позиції $i$. Масиви, отримані після цих обмінів, позначимо $a,b$. Тоді завжди виконується $a_i+b_i=n+1$, але $a,b$ вже не обов'язково є перестановками.

Вам відоме $n$, але невідомі ці два масиви. Ви можете вибрати кілька позицій і поміняти місцями $a_i,b_i$ в них; бібліотека взаємодії повідомить розмахи обох масивів після обмінів. Результат кожного обміну зберігається.

Ваше завдання — відновити масив $a$, яким він був до першого запиту. Якщо повернутий масив збігається з потрібним лише після одночасної заміни кожного його значення $x$ на $n+1-x$, така відповідь також вважається правильною.

Деталі реалізації

Вам не потрібно й не слід реалізовувати функцію main.

У вихідному файлі recover.cpp потрібно підключити заголовний файл range.h і реалізувати таку функцію:

std::vector<int> recover(int c, int n);

• $c$ — номер поточної підзадачі: в офіційних тестах він дорівнює $1,2,3,4$, а в прикладі — $0$. $n$ — довжина масивів. Для кожного тесту бібліотека взаємодії викликає recover рівно один раз.
• Повернуте значення має бути масивом цілих чисел довжини $n$, що представляє $a$ до першого запиту або його повне доповнення.

Ви можете викликати таку функцію:

std::pair<int, int> query(const std::vector<int>& positions);

• Індекси в positions мають бути попарно різними й належати $[0,n-1]$. Дозволено передавати порожній масив.
• Для кожного індексу з positions бібліотека взаємодії один раз міняє місцями поточні $a_i,b_i$, а потім повертає розмах поточного $a$ та розмах поточного $b$. Обміни між запитами накопичуються, але у відповіді потрібно відновити початковий масив до цих обмінів.
• Розмах визначається як різниця між найбільшим і найменшим значеннями масиву. Оскільки завжди виконується $b_i=n+1-a_i$, обидва розмахи обов'язково однакові.
• Кількість викликів query не повинна перевищувати ліміт $Q_{\max}$ для відповідного тесту.

Бібліотека взаємодії не є адаптивною: початкові масиви визначаються до початку recover і не змінюються залежно від ваших запитів. Бібліотека, що використовується для остаточного оцінювання, може відрізнятися від наданої бібліотеки для прикладу. Ваша програма не повинна читати внутрішні дані бібліотеки взаємодії або безпосередньо працювати з потоками стандартного введення та виведення.

Локальне тестування

Помістіть recover.cpp, range.h і файл grader.cpp із вкладення в одну директорію та скомпілюйте їх за стандартом C++17:

g++ grader.cpp recover.cpp -o recover -O2 -std=c++17
./recover < ex_range1.in

Перший рядок, який читає локальна бібліотека взаємодії, містить $c,n,Q_{\max}$; другий — перестановку $p_0,\ldots,p_{n-1}$; третій — $n$ чисел $0/1$, де $1$ означає, що в цій позиції відбувся обмін до початку взаємодії. Через параметри функції вам передаються лише $c,n$; перестановка, позначки обмінів і ліміт запитів безпосередньо вашій програмі не передаються.

Якщо відповідь правильна, локальна бібліотека взаємодії виводить у першому рядку Correct!, а в другому — Queries used: Q, де $Q$ — кількість запитів, використаних під час цього виклику. Якщо відповідь неправильна, вона виводить Wrong answer.; якщо виклик інтерфейсу некоректний, вона також повідомляє причину помилки в потоці стандартних помилок.

Приклади

Вхідні дані 1

0 6 67
3 1 6 4 2 5
0 1 1 0 1 0

Вихідні дані 1

Correct!
Queries used: 16

Пояснення

У прикладі до початку взаємодії $a=(3,6,1,4,5,5)$; його повне доповнення — $(4,1,6,3,2,2)$. Повернення будь-якого з цих масивів є правильною відповіддю. Перший виклик query({}) повертає $(5,5)$. Наведене виведення відповідає результату запуску еталонної програми з вкладення; кількість запитів у різних правильних програм може відрізнятися.

Обмеження

Для всіх тестових даних $1\le n\le 500$.

Кожна підзадача оцінюється за тестом із найменшим множником балів у цій підзадачі; подробиці наведено нижче.

Оцінювання

Якщо відповідь, повернута recover, неправильна, параметри query некоректні або кількість запитів перевищує $Q_{\max}$, за цей тест нараховується $0$ балів.

Інакше в підзадачах $1,2$ за цей тест нараховується повна кількість балів. У підзадачах $3,4$ нехай $Q$ — кількість запитів, фактично використаних у цьому тесті. Множник балів $f(Q)$ обчислюється за такою таблицею:

Кількість балів за підзадачу $3$ дорівнює $40f(Q)$, а за підзадачу $4$ — $40f(Q)$. Остаточний результат округлюється до $3$ знаків після десяткової коми за звичайним правилом округлення.

Обмеження часу: $2\ \mathrm{s}$.

Обмеження пам'яті: $512\ \mathrm{MiB}$.