Петя и Вася придумали систему шифровки для обмена записками. Суть ее заключается в следующем. Дана исходная строка S. S' — циклический сдвиг строки влево (первый символ становится последним, а остальные перемещаются на одну позицию влево), S" — циклический сдвиг строки S' и т.д. Петя с Васей выписывают на листок бесконечную последовательность символов SS'S"S"'.... Если им необходимо зашифровать символ C, то они ищут какое-либо вхождение этого символа в выписанную последовательность и записывают его порядковый номер k. Нумерацию символов они ведут с единицы.

Злоумышленник Коля перехватил сообщение и выкрал исходную строку S. Однако он не может определить, какой символ стоит в последовательности SS'S"S"'... на k-ом месте. Помогите злоумышленнику Коле узнать, какой символ соответствует числу k.

Игра «Палиндромика» набирает все большую популярность в казино Рулеттенбурга. Правила «Палиндромики» довольно просты: в начале игры на листок записывается строка и игроки поочередно стирают первый или последний символ. Побеждает игрок, перед ходом которого строка представляет собой палиндром. Палиндромом называется строка, которая читается одинаково как слева направо, так и справа налево.

Алексей Иванович — азартный игрок, однако вместо участия в игре предпочитает делать ставки. Ему удалось узнать, какая строка будет предложена для игры. Алексею Ивановичу предсказать исход игры при оптимальных действиях обоих игроков не под силу. За помощью он обратился к вам.

Развитие химической науки привело к тому, что высшие фуллерены (сложные молекулы углерода в виде шарика или продолговатой трубки) стали недорогими в производстве. Благодаря своим уникальным оптическим свойствам они нашли свое место и в ювелирной промышленности. Ювелирный дом «Кёрл, Крото и Смолли» выпустил уникальную коллекцию украшений из фуллеренов. Украшение продается в виде набора трубок-фуллеренов различной длины, из которых можно составить украшение самостоятельно.

Норма Джин очень любит сложные углеродные соединения и купила себе набор фуллеренов для составления украшений. Ее фирменный стиль состоит в том, чтобы носить украшения, составленные ровно из трех трубок фуллерена, причем в результате должен получаться тупоугольный треугольник. Норма Джин — объект постоянной охоты папарацци, поэтому не может позволить себе дважды появиться на людях с одним и тем же украшением.

Помогите Норме Джин узнать, сколько вечеров она сможет посетить с имеющимся у нее набором фуллереновых трубок. Фуллереновые трубки одинаковой длины считаются различными. Треугольники считаются различными, если они отличаются хотя бы одной трубкой. Треугольники, состоящие из одних и тех же трубок, считаются одинаковыми независимо от порядка трубок.

Александр недавно увлекся горным туризмом. Ему уже надоело покорять отдельные горные пики, и он собирается покорить самую настоящую горную цепь!

Напомним, что Александр живет в плоском мире. Горная цепь состоит из отрезков, соединяющих точки на плоскости, каждая из которых находится строго правее предыдущей (x-координата следующей точки больше, чем у предыдущей). Трассой на горной цепи называется её часть между двумя фиксированными точками цепи, которые не обязательно являются концами отрезков.

Участок, на котором при движении по трассе координата y (высота) всегда возрастает, называется подъемом, величиной подъема называется разность высот между начальной и конечной точками участка. Ниже изображена горная цепь из 7 точек, на ней задана трасса, которая состоит из четырех участков (трасса выделена жирным). Если проходить трассу слева направо, то один из участков является подъемом.

Туристическая компания предлагает на выбор несколько трасс на одной горной цепи. Александр из-за финансовых трудностей может выбрать для поездки только одну из этих трасс. Вы решили помочь ему с выбором. Александру важно для каждой трассы определить суммарную высоту подъемов на ней.

Напомним, что числами Фибоначчи называется последовательность чисел, получаемая по следующему правилу: f₀ = f₁ = 1, f_k = f_k - 1 + f_k - 2, где k > 1.

Фибоначчиева система счисления (ФСС) — это позиционная система счисления с алфавитом, состоящим из двух цифр: 0 и 1, а ее базисом является последовательность чисел Фибоначчи 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... (f₀ = 1 в базис не включается). В фибоначчиевой системе, как и во всех позиционных системах счисления, «вес» каждого разряда определяется соответствующим элементом базиса этой системы. Так, 10011_fib = 1 × 8 + 0 × 5 + 0 × 3 + 1 × 2 + 1 × 1 = 11. Если не наложить дополнительных ограничений, то представление чисел в такой системе счисления оказывается неоднозначным.

Например, 11₁₀ = 1111_fib = 10011_fib = 10100_fib

Требуется написать программу, которая для натурального числа N будет выводить все его представления в ФСС. Если полученные представления рассматривать как двоичные числа, то выводить их надо в порядке возрастания — от меньшего числа к большему.