Скоро у Лизы день рождения! Родители долго думали, чем порадовать свою любимую дочку, и решили, что лучше всего подарить ей путешествие в Нью-Йорк. Ведь это — такой оригинальный подарок! Так как Лиза — уже самостоятельная девочка, она вполне может сама выбрать, где ей поселиться в Нью-Йорке. Однако родители очень беспокоятся за нее, поэтому они разрешили ей выбирать только из H безопасных пятизвездочных отелей.

Лиза — общительная девочка, и у неё очень много друзей. Узнав, что она будет отмечать день рождения в Нью-Йорке, друзья немедленно отправились туда и поселились в C хостелах.

Лиза по случаю дня рождения устраивает маленькую вечеринку. К сожалению, никто из её друзей не хочет пропустить очередную серию нового реалити-шоу «Home-2», но как только серия закончится, все они одновременно выйдут из своих хостелов и поедут поздравлять Лизу. Она — девочка нетерпеливая, поэтому хочет выбрать отель так, чтобы последний друг приехал к ней как можно раньше, т.е. находился как можно ближе. Так как она тоже не хочет отвлекаться от просмотра высокоинтеллектуального шоу, она попросила вас помочь ей с выбором отеля. Конечно, за это она тоже пригласит вас на вечеринку!

Как известно, Нью-Йорк представляет собой идеальную прямоугольную сетку улиц: с севера на юг тянутся N авеню, а с запада на восток — M улиц. Наличием Бродвея мы в этой задаче пренебрежем. Можно считать, что каждый объект находится в узле этой сетки (и, таким образом, однозначно задается номером авеню и номером улицы, возле пересечения которых он расположен), а два соседних узла сетки находятся на расстоянии одного километра.

Как-то раз удав, слонёнок, мартышка и попугай играли в замечательную игру <<змейка>>.

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

Как известно, измерять длину удава можно в слонятах, мартышках или попугаях. Но в попугаях удав выходит гора-а-а-здо длиннее, поэтому мы остановимся на них в качестве единицы измерения. Поле представляет собой прямоугольную сетку из \)10\( строк по \)10\( ячеек размером \)1\( попугай \)\times\( \)1\( попугай. Изначально длина удава составляет всего три попугая (каким образом удав становится таким коротким в начале игры - долгая и запутанная история, поэтому мы не будем на ней останавливаться в рамках этой задачи), он занимает три крайних левых ячейки в верхней строке поля и смотрит направо. Каждый раз, съедая яблоко, удав удлиняется на одного попугая и занимает, таким образом, ещё одну клетку поля.

Более формально, удав длины \)L\( попугаев представляет собой последовательность из \)L\( различных клеток поля \)A_1, A_2, \ldots, A_L\( таких, что любые две соседние в этой последовательности клетки \)A_i\( и \)A_{i+1}\( являются соседними на поле, т.е. имеют общую сторону. Головой удава считается клетка \)A_L\(. За один ход удав может продвинуться на одну клетку: он выбирает новую клетку \)H\( для своей головы (естественно, смежную с текущей клеткой головы \)A_L\( и не выходящую за границы поля), а его хвост подтягивается следом на одну клетку. То есть, после хода удав будет представлять собой последовательность из клеток \)A_2, A_3, \ldots, A_L, H\(. Обратите внимание, по определению выше удав после выполнения хода не должен дважды содержать одну и ту же клетку, но новое положение головы \)H\( вполне может совпадать со старым положением хвоста \)A_1\( (наш удав перемещается подобно гусенице, сначала сжимаясь и подтягивая хвост, а потом разжимаясь и продвигая голову, поэтому это корректный ход).

Заметим, что из этого определения сразу следует, что в каждый момент времени у удава есть возможность пойти в не более чем трёх направлениях - продолжить движение в направлении, куда смотрит его голова, свернуть налево или свернуть направо.

Перед каждым ходом удава на поле находится ровно одно яблоко. Каждый раз, когда удав съедает яблоко, его длина увеличивается на одного попугая. Это происходит следующим образом: удав делает ход, и если после этого в какой-нибудь из клеток удава (т.е. из клеток \)A_2, A_3, \ldots, A_L, H\( в обозначениях выше) оказывается яблоко, оно считается съеденным (как именно удав может есть яблоки любой частью своего тела - не менее запутанная история, чем объяснение таким скромным размерам удава в начале игры, поэтому её мы также опустим). Если яблоко было съедено, то оно продвигается по телу удава вплоть до бывшего положения хвоста (т.е. до клетки \)A_1\(), и на этом месте возникает новая клетка удава. Таким образом, удав приобретает длину в \)(L + 1)\( попугай и занимает к началу следующего хода клетки (\)A_1, A_2, \ldots A_K, H\(). В этот же момент попугай скидывает следующее яблоко на поле. Обратите внимание, что если удав ест яблоко, то в этом случае он уже не имеет права выбирать в качестве нового положения головы \)H\( старую клетку своего хвоста, потому что тогда к началу следующего хода она будет дважды встречаться в теле удава, что недопустимо!

Удав проигрывает, если он делает некорректный ход. Некто (не будем говорить, кто, хотя это был слонёнок) рассказал вам, в какие клетки поля и в каком порядке попугай собирается скидывать яблоки. Помогите удаву построить выигрышную стратегию перемещения!

Шарик несколько раз запускают с разных стартовых позиций. Для каждого запуска требуется найти x-координаты точки соприкосновения шарика с землёй.

2
0 7 1 3
3 3 4 7
2
2
4

2
3

2
-3 5 1 3
-1 1 1 2
3
-3
-4
1

-1
-4
-1

7
-2 10 2 11
-4 9 -1 6
3 9 8 8
-7 3 -6 6
-1 5 3 4
-3 4 0 3
1 2 7 3
1
0

1