Это интерактивная задача.

На прилавке кондитерской блох стоят два ряда разноцветного двухслойного желе (верхний слой — $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]$. Разрешается передавать пустой массив.
• Библиотека взаимодействия один раз меняет местами текущие $a_i,b_i$ для каждого индекса в positions, затем возвращает размах текущего массива $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}$.