Что может быть проще простого числа? Казалось бы, объяснить, что такое простое число, можно даже человеку, совершенно далёкому от математики: целое число называется простым , если оно не меньше двух и не делится ни на какое целое положительное число, кроме единицы и самого себя. Это определение будет понятно даже третьекласснику, только-только познакомившемуся с делением. Что может быть проще? Но, как часто случается в математике, за кажущейся простотой определения скрывается очень глубокая теория с множеством нетривиальных фактов, многие из которых остаются недоказанными и по сей день.

Леопольд очень интересуется всем, что связано с простыми числами. Недавно он узнал про Постулат Бертрана — оказывается, на отрезке между N и 2 N всегда найдётся хотя бы одно простое число! Несмотря на простую формулировку и интуитивную очевидность этого утверждения, сформулированного французским математиком Жозефом Луи Франсуа Бертраном, оно было доказано только в середине 19 века русским математиком Пафнутием Львовичем Чебышёвым.

Впечатлённый тем, как можно увековечить своя имя на страницах истории математики, Леопольд решил выдвинуть какую-нибудь не менее важную и серьёзную гипотезу, а потом доказать её, и назвать полученный факт теоремой Леопольда. Для этого ему нужна помощь в отыскании закономерностей, описывающих простые числа. Он просит вас написать для него программу, которая ищет отрезок из L последовательных натуральных чисел, содержащий ровно K простых чисел. Чтобы результаты было легче анализировать, он просит вас ограничиться в поисках первыми тридцатью тысячами натуральных чисел. Помогите ему, и, возможно, и вам удастся оставить след в истории!

Склад завода по изготовлению матрёшек переполнен! Нужно как-то освобождать место, поэтому директор завода принял волевое решение продать абсолютно всё, что там лежит. Больше всего места на складе занимают заготовки для матрёшек — нераскрашенные статуэтки целых положительных размеров, которые можно вставлять друг в друга, если размер одной меньше чем размер другой. Увы, в таком неприглядном виде покупать их никто не хочет.

К счастью, завод сотрудничает с союзом художников по матрёшкам. В частности, был заключён договор, позволяющий заводу заказывать роспись матрёшек. В договоре указано, что матрёшка — это упорядоченный набор из M статуэток ( 1 ≤ M ) размеров r ₁ < r ₂ < r ₃ < ... < r _M . Там же прописано, что стоимость раскрашивания одной матрёшки равна одному тугрику, при этом количество статуэток, входящих в матрёшку, значения не имеет.

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

В одном уездном городе Эн было решено построить собственное метро. Все силы города были мобилизованы на выкапывание станций и прокладку подземных путей дедовскими лопатами.

Вся эта история нас бы совершенно не интересовала, если бы однажды в мэрию города не пришло письмо из далёкой страны Емакира. Оказалось, что компания Alpep подозревает администрацию уездного города в нарушении их патента на jMetro и грозится возбудить против города Н дело. Согласно патенту, jMetro — это метро, в котором:

• существует ровно одна узловая станция, в которой начинаются все радиальные линии метро, и это единственная станция, принадлежащая хотя бы двум радиальным линиям;
• количество радиальных линий не меньше пяти;
• существует ровно одна кольцевая линия, все станции которой лежат на радиальных линиях, причём на каждой радиальной линии лежит ровно одна станция кольцевой линии;
• кольцевая линия не проходит через узловую станцию;
• кольцевая линия не проходит через конечные станции радиальных линий.

Поскольку компания Alpep известна своими необоснованными обвинениями в нарушениях патентов, мэрия города хочет проверить правомочность заявления компании.

Лена - страстная любительница пасьянсов. Больше других ей нравятся стандартные пасьянсы на её стареньком рабочем компьютере под управлением доисторической операционной системы <<вай-вай-вай-крософт миндоус 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) .
• Добежав до новой позиции, играющий берет букву, лежащую на подносе около этого места, и клеит ее себе на лоб после предыдущей наклеенной буквы. Таким образом, у него на лбу образуется строка.
• Такие перебежки вокруг стола повторяются до тех пор, пока игра не закончится.
• Игра заканчивается в тот момент, когда строка на лбу кого-то из игроков (обязательно только у одного) оказывается в алфавитном порядке меньше, чем все строчки на всех остальных лбах. Этот игрок становится победителем.

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