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

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

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

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

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

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

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

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

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

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

Удав проигрывает, если он делает некорректный ход. Помогите удаву cъесть все яблоки!

Примечание

Пояснение к первому тесту. Положение удава по ходу игры показано ниже.

Пояснение ко второму тесту. Обратите внимание, что после шестого хода происходит ситуация, проиллюстрированная в условии: в качестве нового положения головы выбирается клетка \((2, 3)\), являющаяся на тот момент клеткой хвоста.