ЕЖЕГОДНАЯ ОЛИМПИАДА ПО ПРОГРАМИРОВАНИЮ В ЛИЧНОМ ЗАЧЁТЕ

11 мая регистрация участников на сайте http:\olimp.bstu.by
Дата проведения 17 мая
Время проведения с 9:00 до 12:00

 
HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > VIII ОЛИМПИАДА БрГТУ ПО ПРОГРАММИРОВАНИЮ ДЛЯ ШКОЛЬНИКОВ - очный тур > problem:


C. Развивающие игры

VIII ОЛИМПИАДА БрГТУ ПО ПРОГРАММИРОВАНИЮ ДЛЯ ШКОЛЬНИКОВ - очный тур

Start: Feb.26.2022 at 10:30:00 AM
Finish: Feb.26.2022 at 01:30:00 PM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (1)

Contest problems

• A. Подсчёт столбов
• B. В гору пойдет!
• C. Развивающие игры
• D. Вечеринка в Нью-Йорке
• E. Сладкоежка
• F. Проще простого

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/2000/2000/2000 ms. Memory limit 256000/256000/256000/256000 Kb.

Развивающие игры
Развивающие игры
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
games.in
вывод
games.out

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

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

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

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

Входные данные

В первой строке входного файла содержатся два целых числа N и K. 1 ≤ N ≤ 3·105, |K| ≤ 3·105. Следующая строка входного файла содержит строку из N строчных латинских букв. Первая буква соответствует буквам, лежащим на подносе перед первым игроком, вторая — перед вторым и так далее.

Выходные данные

Если игра с имеющимися начальными данными когда-нибудь закончится, то выведите в первой строке слово «Finite» (без кавычек), а во второй строке номер победителя (игроки нумеруются начиная с единицы). В случае, если ребята обречены бегать бесконечно, выведите в первой строке слово «Infinite» (без кавычек), а во второй строке выведите номера игроков, которые на момент наступления Апокалипсиса будут иметь лексикографически минимальные строки на своих лбах. Номера необходимо выводить в возрастающем порядке. Игроки нумеруются с единицы.

Примеры

Входные данные

Выходные данные

3 3

aba

Infinite

1 3

3 2

a b a

Finite

1

5 0

break

Finite

4

 

Для отправки решений необходимо выполнить вход.

www.contester.ru