Последнее время Поликарп стал часто пропускать сигналы своего будильника, всего лишь нужно было ввести комбинацию 4 8 15 16 23 42 и можно дальше сладко спать. К сожалению, он стал часто просыпать важные дела и решил покончить с этим.

На днях Поликарп купил себе новый будильник, представляющий из себя хитрое устройство, которое просто так не выключишь. Чтобы будильник перестал работать нужно ввести десятичное число, состоящее из цифр 0 и 1, которое будет делиться нацело на все свои циклические сдвиги. Циклический сдвиг числа — это число, полученное переносом первых нескольких цифр в конец. Например, для числа 4020 это будут числа 4020, 204, 2040 и 402.

Всё было бы так просто, если бы будильник не требовал каждый раз новую комбинацию. Поэтому Поликарп решил вводить каждое утро числа по порядку, начиная с числа 1. Но, он беспокоится, что у него когда-нибудь не получится ввести нужное число, поэтому Поликарп решил узнать K-ое по порядку число заранее. Помогите ему, он в долгу не останется.

Поликарп забыл свой пароль, но он помнит, что пароль является десятичным числом. В записи числа присутствуют только ненулевые цифры, причём все они различны. Чтобы усложнить пароль, Поликарп выбрал среди всех вариантов самое большое чётное число. Помогите Поликарпу вспомнить пароль, если известно, что его длина равна n.

Поликарп недавно принял участие в одном престижном турнире по программированию но, к сожалению не смог в нём выиграть. Осознав свою ошибку — недостаток опыта в олимпиадах, он решил потренироваться до следующего сезона. Просмотрев десятки сайтов и форумов по олимпиадному программированию, он подготовил список соревнований и онлайн тренировок. Про каждое соревнование Поликарп записал название и даты начала и конца.

Когда Поликарп изучал форумы, он заметил, что все соревнования можно оценить по интересности. Он понял, что интересность олимпиады напрямую зависит от количества буквы «C» в аббревиатуре названия этой олимпиады. Если её совсем нет, Поликарп считает это соревнование скучным. Если присутствует хотя бы одна буква «C», то соревнование вполне интересное, а если их больше одной, то соревнование считается действительно достойным. Так как название олимпиады состоит из набора слов, то аббревиатура строится следующим образом: для каждого слова в названии определяется, из каких букв оно состоит, если только из заглавных, то слово полностью входит в аббревиатуру, иначе входит только первая буква слова в заглавной форме. Например, для названия «Russian AI cup» аббревиатурой будет «RAIC».

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

Поликарп на днях приобрёл себе домашнего робота-андроида. Купил он его на распродаже, при чём одну из немногих моделей — со встроенной кофе-машиной. Но в первые же дни он начал замечать, что зарядки его андроида хватает лишь на сутки, хотя в документации сказано, что её должно хватать на неделю. Обратившись в техподдержку, Поликарп выяснил, что функциональность робота зависит от кода прошивки, который записан в его памяти. Код представляет из себя строку из букв латинского алфавита. Изучив документацию на официальном сайте разработчиков, Поликарп нашёл код прошивки, который позволяет разблокировать такие функции, как пылесос, огнетушитель, которых как раз не хватает Поликарпу, а также продлить время работы до трёх дней, что вполне устроит Поликарпа.

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

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

Поликарпа недавно приняли на работу в одну престижную компанию. На собеседовании ему дали интересное задание:

Даны $$$N$$$ лампочек, выстроенных в ряд. Изначально все они выключены. Далее происходит инверсия каждой первой, потом каждой второй, потом каждой третьей лампочки и так далее до каждой $$$N$$$-й. Требуется узнать сколько лампочек будет гореть после проделанных инверсий. Под инверсией понимается изменение состояния с «включено» на «выключено» и наоборот. Поликарп не задумываясь выдал ответ, и его приняли на место главного разработчика модуля, отвечающего за конфигурацию более серьёзных объектов — фонарей.

Скоро день города, поэтому фонари на главном авеню должны гореть не как обычно. Модуль, над которым работает Поликарп, должен принимать запросы вида $$$i$$$, $$$j$$$, $$$k$$$, запрос такого вида обозначает, что нужно применить инверсию к каждому $$$k$$$-му фонарю на отрезке $$$[i,j]$$$. Более точно, произойдёт инверсия $$$i$$$-го, $$$i+k$$$-го, $$$i+2k$$$-го фонаря и так далее. Так как ответственный за подачу команд должен владеть информацией обо всех фонарях, модуль так же должен уметь выводить текущую конфигурацию всех фонарей.

Поликарп считает, что код его модуля идеален, но руководство считает, что он слишком медленно работает, и угрожает Поликарпу должностью полировщика нитей накала. Помогите Поликарпу улучшить его модуль, он в долгу не останется!

Для заданого числа A найти такие N чисел x_i, что и A > x₁ > x₂ > ... > x_N - 1 > x_N ≥ 0.

Если таких вариантов несколько, найдите такой, у которого максимальное x₁, если и таких вариантов больше одного, то тот, у которого максимальное x₂, потом максимальное x₃ и так далее, то есть найдите лексикографически максимальный вариант.