A и B, выбранные в сборную Японии на Международную олимпиаду по информатике, решили сыграть с председателем японского комитета олимпиады K в «Посланника», чтобы улучшить свои навыки обработки информации. Ниже описаны правила игры.

A и B изолированы в комнатах, как показано на рисунке. В комнатах A, B и председателя K есть внутренние телефоны, но звонить может только K. Других средств связи нет, и A и B не могут выходить из своих комнат без указания.

Комната A — длинный коридор — комната председателя K — длинный коридор — комната B.

В начале игры председатель K сообщает A по телефону некоторое положительное целое число $X$. Цель игры — правильно передать значение $X$ от A к B без прямой связи между ними.

В комнате K есть поле $4\times4$. Клетку в строке $i$ и столбце $j$ обозначим $(i,j)$ ($1 \le i \le 4$, $1 \le j \le 4$). Клетка $(1,1)$ — верхний левый угол, $(1,4)$ — верхний правый, $(4,1)$ — нижний левый, $(4,4)$ — нижний правый. В начале игры в некоторую клетку ставится одна фишка. В дальнейшем K сам не меняет положение фишки.

Затем K многократно вызывает A или B по телефону в свою комнату. При каждом посещении A или B обязан переместить фишку в одну из соседних клеток сверху, снизу, слева или справа. После перемещения посетитель возвращается в свою комнату. Если B при посещении комнаты K понял значение $X$, он может вместо перемещения фишки сообщить его K. Правильное значение $X$ означает правильный ответ, а любое другое — неправильный.

K вызывает A и B нерегулярно, и они не знают, в каком порядке он их вызывает. Однако порядок вызовов K определяет в начале игры; гарантируется, что он не вызывает одного из игроков более $100$ раз подряд. Если после суммарно $10\,000$ вызовов, к моменту возвращения A или B в свою комнату, B ещё не сообщил значение $X$, игра заканчивается с неправильным ответом.

Задание

Реализуйте стратегии A и B и напишите программу, которая даёт правильный ответ в описанной игре «Посланник».

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

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

Первый файл называется playerA.c или playerA.cpp. Он реализует стратегию A и должен содержать следующие процедуры.

• void InitA(int T, int X)

  Эта процедура вызывается один раз в начале. Аргумент T — номер подзадачи $T$. Аргумент X — положительное целое число $X$, которое A должен передать B.

• int GameA(int I, int J)

  Процедура вызывается, когда A приходит в комнату K. Аргументы I,J задают пару целых чисел $(I,J)$ — клетку с фишкой в этот момент. Выполняются $1 \le I \le 4$ и $1 \le J \le 4$.

  Процедура должна вернуть одно из целых чисел $-1,-2,-3,-4$. Иное значение приводит к неправильному ответу [1] и завершению программы. Эти значения обозначают следующие действия A.

  • $-1$: переместить фишку вверх в клетку $(I-1,J)$.
  • $-2$: переместить фишку вниз в клетку $(I+1,J)$.
  • $-3$: переместить фишку влево в клетку $(I,J-1)$.
  • $-4$: переместить фишку вправо в клетку $(I,J+1)$.

  Если указанное перемещение выводит фишку за пределы поля, выставляется неправильный ответ [2], и программа завершается.

Второй файл называется playerB.c или playerB.cpp. Он реализует стратегию B и должен содержать следующие процедуры.

• void InitB(int T)

  Эта процедура вызывается один раз в начале. Аргумент T — номер подзадачи $T$.

• int GameB(int I, int J)

  Процедура вызывается, когда B приходит в комнату K. Аргументы I,J задают пару целых чисел $(I,J)$ — клетку с фишкой в этот момент. Выполняются $1 \le I \le 4$ и $1 \le J \le 4$.

  Процедура должна вернуть одно из целых чисел $-1,-2,-3,-4$ либо положительное целое число $Y$. Иное значение приводит к неправильному ответу [3] и завершению программы. Эти значения обозначают следующие действия B.

  • $-1$: переместить фишку вверх в клетку $(I-1,J)$.
  • $-2$: переместить фишку вниз в клетку $(I+1,J)$.
  • $-3$: переместить фишку влево в клетку $(I,J-1)$.
  • $-4$: переместить фишку вправо в клетку $(I,J+1)$.

  Если указанное перемещение выводит фишку за пределы поля, выставляется неправильный ответ [4], и программа завершается.

  • Положительное целое число $Y$: сообщить председателю K, что значение $X$ равно $Y$. Если $X=Y$, ответ правильный; иначе выставляется неправильный ответ [5]. После этого программа завершается.

Ни одна из процедур GameA и GameB не вызывается более $100$ раз подряд. Если после суммарно $10\,000$ вызовов GameA и GameB процедура GameB ещё не вернула положительное целое число, выставляется неправильный ответ [6], и программа завершается.

Можно реализовывать другие внутренние процедуры и объявлять глобальные переменные. Однако два представленных файла компонуются с проверяющей программой в один исполняемый файл. Поэтому все глобальные переменные и внутренние процедуры в каждом файле нужно объявлять с static, чтобы избежать конфликтов с другими файлами. При проверке программа запускается как два процесса, представляющих A и B, поэтому глобальные переменные между сторонами A и B не разделяются.

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

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

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

Пример проверяющей программы состоит из одного файла: grader.c или grader.cpp. Для тестирования выполните следующие команды.

• Для C

  gcc -O2 -lm grader.c playerA.c playerB.c -o grader

• Для C++

  g++ -O2 -lm grader.cpp playerA.cpp playerB.cpp -o grader

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

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

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

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

• Первая строка содержит целые числа $T,X,I_0,J_0$, разделённые пробелами. Они означают номер подзадачи $T$, число $X$, которое A должен передать B, и начальное положение фишки $(I_0,J_0)$.
• Вторая строка содержит строку ровно из $10\,000$ символов A и B. Если $k$-й символ ($1 \le k \le 10\,000$) равен A или B, то $k$-й вызов после вызовов InitA и InitB будет вызовом соответственно GameA или GameB.

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

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

• При правильном ответе выводится Accepted. Кавычки не выводятся; далее действует то же правило.
• При неправильном ответе его тип выводится по номеру из раздела «Детали реализации», например Wrong Answer [1]. Для неправильного ответа [5] дополнительно выводятся правильное значение $X$ и положительное целое число $Y$, возвращённое GameB, например Wrong Answer [5] : X = 2, Y = 3.

Ограничения

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

• $1 \le X \le 1\,000\,000\,000$.

Подзадачи

Подзадача 1 [20 баллов]

• $T=1$.
• Первым в комнату K вызывается A, а затем A и B вызываются по очереди. То есть после InitA и InitB процедуры вызываются в порядке GameA, GameB, GameA, GameB, ...

Подзадача 2 [20 баллов]

• $T=2$.
• Начальное положение фишки — $(I_0,J_0)=(1,1)$. То есть после InitA и InitB сначала вызывается GameA или GameB с аргументами $I=1,J=1$.

Подзадача 3 [60 баллов]

• $T=3$.

Примеры

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

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

2 6 1 1
ABBAABAAABBBBBABBAABBBABBBBAAAAABABAABAABBBBABAAAA

Далее строка опущена.

Пример вызовов

Учтите, что этот пример не обязательно описывает осмысленное взаимодействие.