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

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

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

В данной игре можно считать, что ребята выполняют все движения синхронно, а буквы на подносах бесконечны, как и свободное место на лбу каждого участника.

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