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

Алиса и Боб играют в игру с угадыванием чисел. Сначала Алиса выбирает $b\in\{0,1\}$, при этом Боб не знает значения $b$. Затем Алиса генерирует перестановку на множестве $\{0,1\}^{64}$ следующим образом:

• Если $b=0$, то $P$ выбирается равномерно случайно из всех перестановок на $\{0,1\}^{64}$.
• Если $b=1$:
  • $f_1,f_2,f_3$ выбираются независимо и равномерно случайно из всех функций вида $\{0,1\}^{32}\to\{0,1\}^{32}$.
  • Чтобы вычислить $P(x)$, Алиса сначала разбивает $x$ на $x=x_0\circ x_1$, где $x_0, x_1$ имеют длину по 32 бита.
  • Алиса выполняет следующие вычисления:
    • $x_2=x_0\oplus f_1(x_1)$
    • $x_3=x_1\oplus f_2(x_2)$
    • $x_4=x_2\oplus f_3(x_3)$
  • Алиса выдает $x_3\circ x_4$ в качестве результата $P(x)$. Иными словами, $P(x_0\circ x_1)=x_3\circ x_4$, где $x_3, x_4$ определены выше.

Нетрудно заметить, что в обоих случаях полученная $P$ является корректно определенной перестановкой. Теперь Бобу нужно определить значение $b$. Он может делать Алисе запросы двух типов:

• Боб выбирает любое $x\in\{0,1\}^{64}$ и запрашивает $P(x)$.
• Боб выбирает любое $x\in\{0,1\}^{64}$ и запрашивает $P^{-1}(x)$.

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

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

Данная задача поддерживает только c++. В вашем исходном файле необходимо подключить interaction.h (см. прилагаемые файлы). Интерфейсные функции для взаимодействия определены следующим образом:

/**
 * @brief Queries P(x) or P^{-1}(x)
 * @param x The value to query
 * @param rev Set rev=0 to query P(x), rev=1 to query P^{-1}(x)
 * @return P(x) for rev=0, P^{-1}(x) for rev=1
 */
unsigned long long getperm(unsigned long long x,int rev);
/**
 * @brief Make no more than 256 calls to getperm, to guess b
 * @see getperm
 * @return The b you guesses
 */
int guessb();

Вы должны реализовать функцию int guessb() в своем исходном файле. Она должна выполнять не более $256$ запросов, вызывая getperm, и возвращать $0/1$ в качестве предположения о значении $b$. Если что-то осталось неясным, в прилагаемых файлах есть простая реализация permutation.cpp, которую вы можете использовать в качестве основы для своего решения.

Компиляция и запуск

Используйте

g++ -o grader grader.cpp permutation.cpp

для компиляции вашего исходного файла вместе с библиотекой взаимодействия, чтобы получить исполняемый файл grader. Здесь permutation.cpp — имя вашего локального исходного файла.

Затем для Linux/MacOS используйте

./grader

для запуска; для Windows используйте

grader.exe

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

Каждый тест содержит несколько наборов данных.

Первая строка содержит целое положительное число $t$, количество наборов данных.

Вторая строка содержит два 64-битных беззнаковых целых числа $s_0,s_1$ ($0\le s_0,s_1\le 2^{64}-1$), представляющих начальные значения (seed) для генератора случайных чисел, используемого в grader.

Это работа grader.cpp. Вы не должны считывать какие-либо данные из стандартного ввода в своем исходном файле.

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

Для каждого набора данных выводится одна строка. Если было сделано более 256 запросов, выводится QLE. В противном случае, если предположение о $b$ верно, выводится OK; если неверно — WA.

Это работа grader.cpp. Вы не должны записывать какие-либо данные в стандартный вывод в своем исходном файле.

Ограничения

Для 20% тестов $t=1$.

Для следующих 20% тестов $t=4$.

Для оставшихся 60% тестов $t=100$.

Мы гарантируем, что общее время, необходимое grader.cpp на обработку $25600$ запросов, не превышает 10 мс.

О представлении двоичных строк целыми числами: мы договорились, что младший бит целого числа соответствует первому двоичному символу, а старший бит — последнему. Таким образом, для $x=x_0\circ x_1$, $x_0$ — это младшие 32 бита $x$, а $x_1$ — старшие 32 бита $x$. Например, для x=0xFEDCBA9876543210 мы имеем x_0=0x76543210 и x_1=0xFEDCBA98. То же самое верно для $x_3\circ x_4$.

Примечание

Прилагаемый grader.cpp предназначен только для ознакомления. При тестировании на сервере мы будем использовать другой grader.cpp (с гарантией идентичности интерфейса). Ваш исходный файл должен обращаться только к интерфейсам, предоставленным в interaction.h, и не должен пытаться получить доступ к внутренним компонентам grader.cpp.