D2. Разбиение XOR — игровая версия
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

Алиса и Боб играют в игру. Игра начинается с целого числа $$$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$$$ обозначает операцию побитового исключающего ИЛИ.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных.

Единственная строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \leq n \leq 10^{18}$$$) — число, с которого начинается игра.

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

Для каждого тестового случая, взаимодействие начинается с чтения целого числа $$$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
1

0 0
3


0 0
13


3 4

0 0
777777770001


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


second


first
2 1


first
10 7

1 2


first
777777770000 1
Примечание

Пояснения по взаимодействию.

Интерактор / БобАлисаПояснение
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$$$ и совершить операцию разбиения, но он сдался.