Привидение Петя любит играть со своими кубиками. Он любит выкладывать их в ряд и разглядывать свое творение. Однако недавно друзья решили подшутить над Петей и поставили в его игровой комнате зеркало. Ведь всем известно, что привидения не отражаются в зеркале! А кубики отражаются. Теперь Петя видит перед собой N цветных кубиков, но не знает, какие из этих кубиков настоящие, а какие — всего лишь отражение в зеркале. Помогите Пете! Выясните, сколько кубиков может быть у Пети. Петя видит отражение всех кубиков в зеркале и часть кубиков, которая находится перед ним. Часть кубиков может быть позади Пети, их он не видит.

Известно, что в солнечной системе есть 8 планет и один планетоид. Мало кто знает, что ещё есть секретная планета, населенная медведями. Именно туда ассоциация Savez отправляет бравого генерала Хенрика для изучения медведей. Выяснилось, что медведи умеют телепортироваться. Расчётливый генерал Хедрик решил завербовать их в свою армию.

У одного медведя есть N строк (обозначим i -ю из них x _i ). Исследования показывают, что количество раз, которое может телепортироваться медведь равно длине наибольшей подпоследовательности этих строк, удовлетворяющей такому правилу: строки x _i и x _j ( i < j ) могут принадлежать одной такой последовательности, если x _i является и префиксом, и суффиксом x _j .

Помогите уставшему от долгого полёта генералу Хендрику определить, сколько телепортаций сможет сделать данный медведь.

Строка \(s\) назывется префиксом строки \(t\), если строка \(t\) начинается со строки \(s\). Строка \(s\) назывется суффиксом строки \(t\), если строка \(t\) заканчивается на строку \(s\).

Назовём две строки \(s\) и \(t\) циклически эквивалентными, если существует циклический сдвиг, переводящий строку \(s\) в строку \(t\); другими словами строки \(s\) и \(t\) циклически эквивалентны тогда и только тогда, когда, строка \(s\) может быть получена из строки \(t\) путем перемещения некого суффикса строки \(t\) в начало строки \(t\). Например, строки \(ababba\) и \(abbaab\) циклически эквивалентны, в то время как строки \(ababba\) и \(ababab\) нет. В частности, любая строка циклически эквивалентна самой себе.

Дана строка \(t\) длины \(n\). Требуется найти такой префикс \(p\) и такой суффикс \(s\) строки \(t\), что:

• \(p\) циклически эквивалентен \(s\) (и, как следствие, их длины равны)
• длина \(p\) не превосходит \(\frac{n}{2}\) (то есть \(p\) и \(s\) не пересекаются в \(t\))
• длина \(p\) максимальна

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

Логотип состоит из \(n\) вертикальных полос различной высоты. Полосы пронумерованы от \(1\) до \(n\) слева направо. Логотип описывается перестановкой \((s_1, s_2, ..., s_n)\) чисел \(1, 2, ..., n\). Полоса с номером \(s_1\) - самая низкая, полоса с номером \(s_2\) - следующая по высоте и, наконец, полоса \(s_n\) - самая высокая. Фактическая высота полос не имеет большого значения. Вдоль главной улицы расположено \(m\) зданий. К вашему удивлению, высота зданий различна. Задача состоит в том, чтобы найти все позиции, на которых логотип соответствует зданиям. Помогите компании и найдите все непрерывные последовательности зданий, которые соответствуют логотипу. Непрерывная последовательность зданий соответствует логотипу, если здание \(s_1\) в этой последовательности является самым низким, здание \(s_2\) является следующим по высоте и т. д. Например, последовательность зданий высотой \(5, 10, 4\) соответствует логотипу, описанному перестановкой \((3, 1, 2)\), поскольку здание №3 (высотой 4) является самым низким, здание №1 - вторым по высоте, а здание №2 - самым высоким.

Байтазар, король Байтотии организовал масштабную реформу имён своих подданных. Имена жителей Байтотии исторически часто содержат повторяющиеся фразы и Байтазар хочет с одной стороны упростить имена, а с другой, сохранить традиции повторения, а именно Байтазар хочет заменить каждое из имён в Байтотии на имя такой же длины, чтобы при этом множества периодов для старого и нового имён совпали, но имя при этом состояло только из символов «0» и «1». Из всех кандидатов в новое имя Байтазар хочет выбрать лексикографически минимальное.

Натуральное число \(k\) (\(1 \le k \lt n\)) называется периодом строки \(s\) длины \(n\) тогда и только тогда, когда для любого натурального \(i\), такого что \(1 \le i \le n - k\), верно что \(s_i = s_{i + k}\).

Множество периодов для данной строки \(s\) – множество таких чисел \(i\), что \(i\) является периодом \(s\). Обозначим его за Per(\(s\)). К примеру, Per(«ABIABUABIAB») = {6, 9}, Per(«0000») = {1, 2, 3}.

Помогите Байтазару перевести имена его подданных, и, возможно, он разрешит вам сохранить ваше собственное имя!