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$. Якщо викликати функцію з параметром поза цим діапазоном, програма одержить вердикт Wrong Answer[1]. Не можна викликати цю функцію більше одного разу з однаковим параметром pos. Якщо викликати її більше одного разу з однаковим параметром, програма одержить вердикт Wrong Answer[2].
• Параметр bit — значення, що встановлюється в позицію pos послідовності. Значення bit має бути $0$ або $1$. Якщо викликати функцію з іншим значенням, програма одержить вердикт Wrong Answer[3].

Функцію Set потрібно викликати рівно $N$ разів у функції Anna. Якщо після завершення функції Anna кількість викликів Set відрізняється від $N$, програма одержить вердикт Wrong Answer[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$ і повернути його.

Процедура перевірки

Перевірка відбувається так. Якщо програма одержує вердикт Wrong Answer, її виконання негайно припиняється.

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) процедури перевірки.
• Програма не повинна одержувати вердикт Wrong Answer під час виклику 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, приклад перевіряльної програми виводить його тип у такому вигляді: «Wrong Answer [1]», і виконання вашої програми припиняється.
• Якщо жоден виклик функції Anna не одержує вердикт Wrong Answer, приклад перевіряльної програми виводить «Accepted» і значення $L^*$. Про значення $L^*$ див. розділ «Оцінювання».

Якщо програма одержує кілька типів вердикту Wrong Answer, приклад перевіряльної програми повідомляє лише один із них.

Обмеження

Усі вхідні дані задовольняють такі умови.

• $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$, для якого Bruno правильно визначає значення $X$ для кожного запиту з $K \le L$.

• Бали за задачу обчислюються так:

  • Якщо $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(...) такі: