Anna и Bruno — археологи. Они исследуют руины в Иране.

Их обязанности распределены так: Anna посещает руины и находит артефакты, а Bruno анализирует результаты в базовом лагере.

Исследование рассчитано на $Q$ ($=1\,000$) дней. Каждый день Anna отправляет результаты Bruno с помощью устройства связи. Результаты каждого дня выражаются целым числом $X$.

Anna может использовать устройство связи только один раз в день. Оно может передать последовательность длины $N$ ($=150$), состоящую из 0 и 1.

Однако устройство сломалось. В последовательности длины $N$ есть несколько неисправных позиций. В неисправной позиции всегда передаётся значение 0 независимо от установленного значения. При отправке последовательности Anna видит расположение неисправных позиций, но Bruno его не знает. Расположение и количество неисправных позиций могут меняться каждый день.

Возникла опасность, что исследование затянется. Поскольку вы являетесь кандидатом на участие в международном соревновании по программированию в Иране, Anna и Bruno просят вас написать программу для передачи результатов исследования.

Задача

Напишите две программы, обеспечивающие связь между Anna и Bruno.

• Получив длину последовательности $N$, передаваемое целое число $X$, количество неисправных позиций $K$ и их расположение $P$, первая программа задаёт последовательность $S$, отправляемую Anna.
• Получив последовательность $A$, принятую Bruno, вторая программа восстанавливает целое число $X$.

В исправной позиции устройства значения последовательностей $S$ и $A$ совпадают. В неисправной позиции последовательность $A$ всегда содержит 0 независимо от значения в последовательности $S$.

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

Необходимо отправить два файла, написанных на одном и том же языке программирования.

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

void Anna( int N, long long X, int K, int P[] )

Для каждого теста эта функция вызывается $Q=1\,000$ раз.

• Параметр N — длина отправляемой последовательности.
• Параметр X — отправляемое целое число.
• Параметр K — количество неисправных позиций.
• Параметр P[] — последовательность длины $K$, описывающая расположение неисправных позиций.

В функции Anna необходимо вызывать следующую функцию.

void Set( int pos, int bit )

Эта функция задаёт бит в последовательности $S$, которая будет отправлена устройством связи.

• Параметр pos — номер задаваемой позиции. Значение pos должно быть целым числом от $0$ до $N-1$ включительно. Обратите внимание: позиции нумеруются с 0. Если при вызове передано значение вне этого диапазона, программа получает вердикт «Неправильный ответ [1]». Нельзя вызывать эту функцию более одного раза с одним и тем же значением pos. Если такой вызов повторяется, программа получает вердикт «Неправильный ответ [2]».
• Параметр bit — значение, устанавливаемое в позиции pos последовательности. Значение bit должно быть равно 0 или 1. При вызове с другим значением программа получает вердикт «Неправильный ответ [3]».

В функции Anna функция Set должна быть вызвана ровно $N$ раз. Если при завершении Anna количество вызовов Set отличается от $N$, программа получает вердикт «Неправильный ответ [4]».

Программа завершается, если вызов функции из Anna признан недопустимым.

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

long long Bruno( int N, int A[] )

Для каждого теста эта функция вызывается $Q=1\,000$ раз.

• Параметр N — длина последовательности, принятой Bruno.
• Параметр A — последовательность целых чисел длины $N$. Это последовательность, принятая Bruno.
• Функция Bruno должна восстановить значение $X$ и вернуть его.

Процедура оценивания

Оценивание выполняется следующим образом. Если программа получает вердикт «Неправильный ответ», она немедленно завершается.

1. Установить cnt = 0.
2. Вызвать функцию Anna один раз.
3. Пусть $S$ — последовательность, заданная функцией Anna. В последовательности $S$ установить 0 в позициях из $P$, получив последовательность $A$. Вызвать функцию Bruno один раз с параметром $A$.
4. Установить cnt = cnt +1. Если $\mathrm{cnt}<Q$, перейти к шагу (2). Если $\mathrm{cnt}=Q$, перейти к шагу (5).
5. Программе начисляются баллы.

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

• Время работы и использование памяти учитываются для шагов (1), (2), (3), (4) процедуры оценивания.
• Программа не должна получать вердикт «Неправильный ответ» при вызове Anna на шаге (2) или Bruno на шаге (3). Программа должна выполняться без ошибок времени исполнения.
• Программа может реализовывать другие функции для внутреннего использования и использовать глобальные переменные. Отправленные программы будут скомпилированы вместе с модулем оценивания в один исполняемый файл. Все глобальные переменные и внутренние функции должны быть объявлены static, чтобы избежать конфликтов с другими файлами. При оценивании программы Anna и Bruno выполняются в двух разных процессах, поэтому они не могут совместно использовать глобальные переменные.
• В процессе каждая из функций Anna и Bruno вызывается $Q=1\,000$ раз. Переменные ваших программ необходимо инициализировать соответствующим образом.
• Программа не должна использовать стандартный ввод и стандартный вывод. Программа не должна никаким способом взаимодействовать с другими файлами.

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

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

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

C

gcc -std=c11 -O2 -o grader grader.c Anna.c Bruno.c -lm

C++

g++ -std=c++14 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

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

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

Входные данные для примера модуля оценивания

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

• Первая строка содержит целое число $Q$.
• Далее задаётся информация о $Q$ запросах.
• Информация о каждом запросе состоит из следующих двух строк.

Первая строка содержит три целых числа $N,X,K$, разделённых пробелами. Это означает, что длина отправляемой последовательности равна $N$, отправляемое Anna число равно $X$, а количество неисправных позиций равно $K$.

Вторая строка содержит $K$ целых чисел $P_0,P_1,\ldots,P_{K-1}$, разделённых пробелами. Это означает, что для каждого $i$ ($0 \le i \le K-1$) позиция $P_i$ последовательности неисправна.

Выходные данные примера модуля оценивания

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

• Если программа получает вердикт «Неправильный ответ», пример модуля оценивания выводит его тип в виде Wrong Answer [1], и завершает программу.
• Если ни один вызов функции Anna не получил вердикт «Неправильный ответ», пример модуля оценивания выводит Accepted и значение $L^*$. Значение $L^*$ описано в разделе «Подзадачи».

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

Ограничения

Все входные данные удовлетворяют следующим условиям.

• $Q=1000$.
• $N=150$.
• $0 \le X \le 1\,000\,000\,000\,000\,000\,000$.
• $1 \le K \le 40$.
• $0 \le P_i \le N-1$ ($0 \le i \le K-1$).
• $P_i < P_{i+1}$ ($0 \le i \le K-2$).

Подзадачи

Пусть $L^*$ — минимум следующего значения по всем тестам этой задачи:

• Наибольшее целое число $L \le 40$, такое что для каждого запроса с $K \le L$ Bruno возвращает правильное значение $X$.

Баллы за задачу вычисляются следующим образом:

• Если $L^*=0$, начисляется 0 баллов.
• Если $1 \le L^* \le 14$, начисляется 8 баллов.
• Если $15 \le L^* \le 37$, начисляется $(L^*-15)\times 2+41$ баллов.
• Если $38 \le L^* \le 40$, начисляется $(L^*-38)\times 5+90$ баллов.

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

Ниже приведены пример входных данных для модуля оценивания и соответствующие вызовы функций. Обратите внимание, что этот пример не удовлетворяет ограничениям задачи, поскольку $Q=2$, $N=3$.

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

2
3 14 1
2
3 9 2
0 1

Вызовы функций

Параметры вызовов Anna(...), Bruno(...), Anna(...), Bruno(...) приведены ниже.