Это интерактивная задача.
Это игровая версия задачи. Обратите внимание, что решение этой задачи может иметь или не иметь общих идей с решением сольной версии. Вы можете сдавать и получать баллы за каждую из версий независимо.
Алиса и Боб играют в игру. Игра начинается с целого числа \(n\). Игроки совершают ходы по очереди. На каждом ходу игры происходит следующая последовательность событий:
- Игрок, имеющий целое число \(p\), разбивает его на два целых числа \(p_{1}\) и \(p_{2}\), где \(0 \lt p_{1} \lt p\), \(0 \lt p_{2} \lt p\) и \(p_{1} \oplus p_{2} = p\).
- Если такие \(p_{1}\), \(p_{2}\) не существуют, то игрок проигрывает.
- Иначе, оппонент выбирает либо \(p_{1}\), либо \(p_{2}\).
- Игра продолжается с выбранным числом. Оппонент будет пытаться разбить его.
Ваша задача помочь Алисе выиграть. Вы можете выполнить не более \(63\) операций разбиения. Вы можете выбрать будет Алиса ходить первой или второй. Система будет играть за Боба.
Здесь \(\oplus\) обозначает операцию побитового исключающего ИЛИ.
Протокол взаимодействия
Для каждого тестового случая, взаимодействие начинается с чтения целого числа \(n\).
После чтения \(n\), выведите отдельную строку, содержащую либо «first», либо «second», обозначив, каким вы хотите начать игру(первым или вторым соответственно).
Во время хода Алисы вы должны вывести два положительных целых числа \(p_{1}\) и \(p_{2}\), такие что \(0 \lt p_{1} \lt p\), \(0 \lt p_{2} \lt p\) и \(p_{1} \oplus p_{2} = p\). Здесь \(p\) должно равняться одному из двух чисел выведенных Бобом на предыдущем ходу. Если до этого не было ходов, то \(p\) равняется \(n\). Если Алиса не может произвести операцию разбиения, выведите «0 0», после чего вы получите вердикт Неправильный ответ.
Во время хода Боба, вы должны прочитать два положительных целых числа \(p_{1}\) и \(p_{2}\), такие что \(0 \lt p_{1} \lt p\), \(0 \lt p_{2} \lt p\) и \(p_{1} \oplus p_{2} = p\). Здесь \(p\) должно равняться одному из двух чисел выведенных Алисой на предыдущем ходу. Если до этого не было ходов, то \(p\) равняется \(n\). Если Боб не может произвести операцию разбиения, \(p_{1} = 0\) and \(p_2 = 0\), в случае чего вы должны перейти к решению следующего тестового случая.
Если операция, совершенная Алисой, некорректна, интерактор выведет «-1 -1» и ваша программа должна завершиться незамедлительно, чтобы получить вердикт Неправильный ответ.
Если Алиса совершает \(63\) хода и Боб все еще может совершить операцию разбиения с текущими числами, интерактор выведете «-1 -1», и ваша программа должна завершиться незамедлительно, чтобы получить вердикт Неправильный ответ.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Вы не можете делать взломы в этой задаче.
Примечание
Пояснения по взаимодействию.
| Интерактор / Боб | Алиса | Пояснение |
| 4 | | \(t\) |
| 1 | | \(n\) для первого тестового случая |
| second | Алиса выбирает начать второй |
| 0 0 | | Боб говорит, что не может разбить \(p = 1\) |
| 3 | | \(n\) для второго тестового случая |
| first | Алиса выбирает начать первой |
| 1 2 | Алиса ломает \(p = 3\) на \(p_1 = 1\) и \(p_2 = 2\) |
| 0 0 | | Боб говорит, что не может разбить ни \(p = 1\), ни \(p = 2\) |
| 13 | | \(n\) для третьего тестового случая |
| first | Алиса выбирает начать первой |
| 10 7 | Алиса ломает \(p = 13\) на \(p_1 = 10\) и \(p_2 = 7\) |
| 3 4 | | Боб ломает \(p = 7\) на \(p_1 = 3\) и \(p_2 = 4\) |
| 1 2 | Алиса ломает \(p = 3\) на \(p_1 = 1\) и \(p_2 = 2\) |
| 0 0 | | Боб говорит, что не может разбить ни \(p = 1\), ни \(p = 2\) |
| 777777770001 | | \(n\) для четвертого тестового случая |
| first | Алиса выбирает начать первой |
| 777777770000 1 | Алиса ломает \(p = 777\,777\,770\,001\) на \(p_1 = 777\,777\,770\,000\) и \(p_2 = 1\) |
| 0 0 | | Боб говорит, что не может совершить операцию разбиения |
Таблица лишь для пояснения формата взаимодействия и не отражает настоящего поведения интерактора.
Обратите внимание, что в последнем тестовом случае Боб мог выбрать \(p_1\) и совершить операцию разбиения, но он сдался.