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

Вам дан список S из k разрешённых слов. Так же вам даны буквы Зига за первые n ходов. На каждую из этих ходов найдите слово, которое Заг должен сказать.

Скажем, что последовательность строк t ₁ , ..., t _k является путешествием длины k , если для всех i > 1 t _i является подстрокой t _{i - 1} строго меньшей длины. Например, { ab , b } является путешествием, а { ab , c } или { a , a } — нет.

Определим путешествие по строке s как путешествие t ₁ , ..., t _k , все строки которого могут быть вложены в s так, чтобы существовали (возможно, пустые) строки u ₁ , ..., u _{k + 1} , такие, что s = u ₁ t ₁ u ₂ t ₂ ... u _k t _k u _{k + 1} . К примеру, { ab , b } является путешествием по строке для abb , но не для bab , так как соответствующие подстроки расположены справа налево.

Назовём длиной путешествия количество строк, из которых оно состоит. Определите максимально возможную длину путешествия по заданной строке s .

Строка \(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}.

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