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

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

• 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\( старую клетку своего хвоста, потому что тогда к началу следующего хода она будет дважды встречаться в теле удава, что недопустимо!

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

В одном далеком мире, в славном городе Эрбовле открыли новый банк. В банке есть \(m\) сотрудников, работающих с клиентами, и один главный бухгалтер.

Для решения своих проблем в банк приходят гномы. Известно, что \(i\)-й гном приходит в банк через \(t_i\) минут после открытия банка. Сначала ему нужно провести \(a_i\) минут у одного из \(m\) сотрудников, а потом еще \(b_i\) минут в офисе главного бухгалтера.

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

Очередь к сотрудникам общая, при этом гном из очереди идет к первому освободившемуся сотруднику. Если в банк одновременно приходят два гнома, то первым в очередь к сотрудникам встает тот, чей номер меньше. Если гном начал обслуживаться у сотрудника в момент \(x\), то он освобождается в момент \(x+a_i\), в этот момент другой гном может начать обслуживаться у этого же сотрудника. Гном, пришедший в банк в момент \(t\), может начать обслуживаться у сотрудника в любой момент, начиная с \(t\).

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

Сегодня в банк собирается прийти \(n\) гномов, про каждого известно: во сколько он заходит в банк, сколько времени он хочет провести у окошка и сколько времени он хочет провести у бухгалтера. Нужно сообщить время выхода из банка для каждого гнома.

Андрей очень любит играть в Космический покер.

В космическом покере вместо карт используются фишки трех цветов. Казино определяет два числа \(A\) и \(C\) - коэффициенты для вычисления ставок. Затем игрок по определенным правилам ставит фишки трех цветов: красного, зеленого и синего. Выигрыш игрока вычисляется по формуле:
A * (\(r^2\) + \(g^2\) + \(b^2\)) + C * min{\(r\), \(g\), \(b\)}, где \(r\), \(g\), \(b\) - количество фишек красного, зеленого и синего соответственно.

Правила, по которым делаются ставки, очень сложны, но сейчас перед Андреем стоит следующая задача. На поле уже есть \(r\) красных, \(g\) зеленых и \(b\) синих фишек. Прежде чем будет определен его выигрыш, он может добавить на поле ровно одну фишку любого цвета. Помогите ему выбрать цвет фишки, которую следует добавить на поле, чтобы максимизировать выигрыш.