Стреляй!

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

Игра проходит на бесконечном экране, состоящем из клеток. Утка находится в определенной клетке, которая неизвестна игроку.

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

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

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

Каждый выстрел нужно выводить в отдельной строке в виде двух целых чисел i и j через пробел, означающих номер строки и столбца соответственно. Несмотря на то, что поле игры бесконечное, координаты выстрела не должны превышать 10⁹ по абсолютному значению.

После каждого вашего выстрела на ввод подаются два целых числа d_i и d_j, означающие изменение строки и столбца координат утки соответственно.

Если оба этих числа равны нулю, значит вы попали в утку и необходимо завершить программу.

Гарантируется, что изначальные координаты утки не превосходят 10⁶ по абсолютному значению.

Пример

Примечание

Для корректной работы программы после каждой операции вывода данных выводите перевод строки, а также очищайте буфер вывода. Очистка буфера вывода производится следующим образом:

• В языке Pascal: flush(output)
• В С/С++: fflush(stdout) или cout.flush()
• В Java: System.out.flush()
• В Python: sys.stdout.flush() из библиотеки sys
• В C# и Basic: Console.Out.Flush()

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!