Anna и Bruno — мастера азартных игр. Они собираются сыграть с D-taro, который будет ведущим игры.

В этой игре Anna и Bruno находятся в разных комнатах. Они могут общаться друг с другом только с помощью сломанного устройства. D-taro даёт Anna целое число. Цель Anna и Bruno — передать это число от Anna к Bruno с помощью устройства.

В начале игры Anna объявляет целое число $m$ от $1$ до $2\,000$ включительно. Затем они играют $Q$ раундов. Раунд $i$ ($1\le i\le Q$) проходит следующим образом.

1. D-taro даёт Anna целое число $A_i$.
2. Anna вводит в устройство массивы $s_i,t_i$. Каждый элемент массивов $s_i,t_i$ должен быть равен $0$ или $1$. Массивы должны иметь одинаковую длину от $1$ до $m$ включительно.
3. Пусть $u_i$ — массив, полученный из массивов $s_i$ и $t_i$ с помощью перемешивания с сохранением порядка (см. ниже). Устройство отправляет $u_i$ к Bruno.
4. Bruno отправляет D-taro целое число. Если оно совпадает с числом $A_i$, которое D-taro дал Anna, то Anna и Bruno выигрывают этот раунд.

Напишите программы, реализующие стратегии Anna и Bruno, позволяющие им выиграть все $Q$ раундов.

Перемешивание с сохранением порядка

Будем говорить, что массив $Z$ получен из массивов $X$ и $Y$ перемешиванием с сохранением порядка, если элементы $Z$ можно разделить на две группы так, чтобы выполнялись следующие два условия.

• Массив из элементов первой группы в исходном порядке совпадает с массивом $X$.
• Массив из элементов второй группы в исходном порядке совпадает с массивом $Y$.

Например, массив $Z=[1,1,1,0,0,0]$ получается из $X=[1,1,0]$ и $Y=[1,0,0]$ таким перемешиванием: первый, второй и четвёртый элементы $Z$ в исходном порядке образуют массив $[1,1,0]$, а третий, пятый и шестой — массив $[1,0,0]$.

С другой стороны, если $X=[1,1,0]$, $Y=[1,0,0]$ и $Z=[0,0,0,1,1,1]$, то $Z$ не получается из $X$ и $Y$ таким перемешиванием.

Детали реализации

Нужно отправить два файла.

Первый файл — Anna.cpp. Он должен реализовывать стратегию Anna и содержать следующие функции. Программа должна подключать Anna.h директивой препроцессора #include.

• int Declare()

  Эта функция вызывается один раз в начале.

  • Возвращаемое значение — целое число $m$, объявленное Anna.
  • Число $m$ должно быть от $1$ до $2\,000$ включительно. При нарушении этого условия программа получает вердикт Wrong Answer [1].

• std::pair<std::vector<int>, std::vector<int> > Anna(long long A)

  После вызова Declare эта функция вызывается $Q$ раз. Её $i$-й вызов ($1\le i\le Q$) соответствует шагам 1 и 2 раунда $i$.

  • Параметр A — целое число $A_i$, переданное D-taro к Anna.
  • Возвращаемое значение — пара массивов $s_i,t_i$, введённых Anna в устройство.
  • Каждый элемент массивов $s_i,t_i$ должен быть равен $0$ или $1$. При нарушении этого условия программа получает вердикт Wrong Answer [2].
  • Длина каждого из массивов $s_i,t_i$ должна быть от $1$ до $m$ включительно. При нарушении этого условия программа получает вердикт Wrong Answer [3].
  • Массивы $s_i,t_i$ должны иметь одинаковую длину. При нарушении этого условия программа получает вердикт Wrong Answer [4].

Второй файл — Bruno.cpp. Он должен реализовывать стратегию Bruno и содержать следующую функцию. Программа должна подключать Bruno.h директивой препроцессора #include.

• long long Bruno(std::vector<int> u)

  После ввода Anna массивов в устройство эта функция вызывается один раз. Всего она вызывается $Q$ раз. Её $i$-й вызов ($1\le i\le Q$) соответствует шагам 3 и 4 раунда $i$.

  • Параметр u — массив $u_i$, отправленный устройством к Bruno в раунде $i$.
  • Возвращаемое значение — целое число, которое Bruno отправляет D-taro.
  • Возвращаемое значение должно совпадать с целым числом $A_i$, которое D-taro дал Anna. При нарушении этого условия программа получает вердикт Wrong Answer [5].

Важные замечания

• Программа может реализовывать другие функции для внутреннего использования и использовать глобальные переменные. Отправленные файлы будут скомпилированы вместе с проверяющей программой в один исполняемый файл. Все глобальные переменные и внутренние функции следует объявлять в безымянном пространстве имён, чтобы избежать конфликтов с другими файлами. При проверке программа запускается как два процесса: Anna и Bruno. Эти процессы не могут совместно использовать глобальные переменные.
• Программа не должна использовать стандартный ввод и стандартный вывод. Запрещено каким-либо способом обмениваться данными с другими файлами. Однако можно выводить отладочную информацию в стандартный поток ошибок.

Компиляция и тестовый запуск

На странице соревнования можно скачать архив с примером проверяющей программы для тестирования вашего решения. Архив также содержит пример исходного файла вашего решения.

Пример проверяющей программы находится в файле grader.cpp. Чтобы проверить решение, поместите grader.cpp, Anna.cpp, Bruno.cpp, Anna.h, Bruno.h в одну папку и скомпилируйте программы следующей командой.

g++ -std=gnu++17 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

После успешной компиляции будет создан исполняемый файл grader.

Учтите, что настоящая проверяющая программа отличается от примера. Пример запускается одним процессом, читает данные из стандартного ввода и записывает результаты в стандартный вывод.

Входные данные примера проверяющей программы

Пример проверяющей программы читает следующие данные из стандартного ввода.

$$ \begin{gathered} Q\\ A_1\\ A_2\\ \vdots\\ A_Q \end{gathered} $$

Выходные данные примера проверяющей программы

Пример проверяющей программы выводит в стандартный вывод следующую информацию (кавычки служат для наглядности).

• Если программа признана правильной, выводится возвращённое функцией Declare значение $m$, например «Accepted: 2000».
• Если программа получает какой-либо вердикт Wrong Answer, пример проверяющей программы выводит его тип, например «Wrong Answer [1]».

Если программа нарушает несколько условий, соответствующих разным типам Wrong Answer, пример проверяющей программы сообщает только об одном из них.

При запуске примера проверяющей программы перемешивание в каждом раунде вычисляется с помощью псевдослучайных чисел. Результаты не меняются между запусками. Чтобы изменить начальное значение генератора псевдослучайных чисел, запустите пример следующим образом.

./grader 2022

Первый аргумент должен быть целым числом.

Ограничения

• $1\le Q\le 1\,000$.
• $1\le A_i\le 1\,000\,000\,000\,000\,000\,000\ (=10^{18})$ ($1\le i\le Q$).

Подзадачи

1. (5 баллов) $A_i\le 2\,000$ ($1\le i\le Q$).
2. (5 баллов) $A_i\le 4\,000\,000$ ($1\le i\le Q$).
3. (3 балла) $A_i\le 10\,000\,000\ (=10^7)$ ($1\le i\le Q$).
4. (12 баллов) $A_i\le 100\,000\,000\ (=10^8)$ ($1\le i\le Q$).
5. (15 баллов) $A_i\le 100\,000\,000\,000\ (=10^{11})$ ($1\le i\le Q$).

6. (60 баллов) Дополнительных ограничений нет. В этой подзадаче оценка вычисляется следующим образом.

   • Пусть $m^*$ — максимум целых чисел $m$, объявленных Anna во всех тестах этой подзадачи.
   • Оценка определяется следующим образом.

Примеры

Ниже приведены пример входных данных проверяющей программы и соответствующие вызовы функций.

Входные данные 1

2
42
2000

Пример вызовов функций

В этом примере $Q\ (=2)$ раунда. В раунде 1 D-taro даёт Anna целое число $A_1\ (=42)$. В раунде 2 D-taro даёт Anna целое число $A_2\ (=2000)$.

Этот пример входных данных удовлетворяет ограничениям всех подзадач.