Лена - страстная любительница пасьянсов. Больше других ей нравятся стандартные пасьянсы на её стареньком рабочем компьютере под управлением доисторической операционной системы <<вай-вай-вай-крософт миндоус XP>>, из которых особенное предподчтение она отдаёт <<Свободной ячейке>> (другое название этого пасьянса - <<Солитер>>). Все стандартные расклады уже давно решаются Леной за минуту, поэтому в свободное время она придумывает, как бы усложнить правила игры.

Она предлагает вам помочь ей со следующей постановкой. В её игре участвуют \(K\) карт одной масти достоинствами от \(1\) до \(K\). Изначально они лежат в одном из слотов в следующем порядке при перечислении снизу вверх: \(1, K, K - 1, K - 2, \dots, 3, 2\). Цель её пасьянса - переложить все карты кроме единицы в один из свободных слотов в порядке \(K, K - 1, \dots 3, 2\), используя \(N\) дополнительных свободных слотов для стопок и \(F\) слотов для одиночных карт.

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

Лена не может определиться с тем, сколько именно карт может лежать в изначальной стопке и сколько должно быть слотов каждого вида. Она просит вас определить для некоторых наборов \(N\), \(F\) и \(K\), раскладывается ли пасьянс.

У Даши тоже скоро день рождения. Целыми днями она обдумывает, кого бы ей пригласить, какое платье надеть, и пытается угадать, что же ей подарят. А в это время её старший брат Серёжа занят гораздо более печальными мыслями — мама сказала, что именно он будет развлекать детей после застолья.

Подойдя к этому делу со свойственной ему ответственностью, Серёжа разработал игру, призванную повысить навыки детей в работе со строками. Правила этой игры таковы:

• N человек сидят за круглым столом на N мест. Перед каждым игроком лежит поднос с одинаковыми буквами-наклейками.
• Перед началом игры ведущий называет некоторое целое число K .
• Каждый играющий хватает букву, лежащую на подносе, перед которым он сидит, клеит ее себе на лоб, после чего все пробегают K позиций вдоль стола по часовой стрелке (от 1 к N , после N опять следует 1 ). Так, например, если за столом сидят 5 человек, и ведущий называет число 2 , то рассадка меняется с (1, 2, 3, 4, 5) на (4, 5, 1, 2, 3) .
• Добежав до новой позиции, играющий берет букву, лежащую на подносе около этого места, и клеит ее себе на лоб после предыдущей наклеенной буквы. Таким образом, у него на лбу образуется строка.
• Такие перебежки вокруг стола повторяются до тех пор, пока игра не закончится.
• Игра заканчивается в тот момент, когда строка на лбу кого-то из игроков (обязательно только у одного) оказывается в алфавитном порядке меньше, чем все строчки на всех остальных лбах. Этот игрок становится победителем.

Маме эта игра показалась очень забавной, но она сразу заметила два слабых места в плане Серёжи. Во-первых, может случится так, что игра никогда не закончится. Во-вторых, дети носятся очень быстро, и уследить за словами у них на лбах практически невозможно, поэтому ведущий (то есть сам Серёжа) может не заметить победителя. Для того, чтобы избежать подобных неприятностей, Серёжа попросил Вас, как своего друга-программиста, написать программу, предсказывающую исход игры по начальным данным.

Скоро у Лизы день рождения! Родители долго думали, чем порадовать свою любимую дочку, и решили, что лучше всего подарить ей путешествие в Нью-Йорк. Ведь это — такой оригинальный подарок! Так как Лиза — уже самостоятельная девочка, она вполне может сама выбрать, где ей поселиться в Нью-Йорке. Однако родители очень беспокоятся за нее, поэтому они разрешили ей выбирать только из 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\( старую клетку своего хвоста, потому что тогда к началу следующего хода она будет дважды встречаться в теле удава, что недопустимо!

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