Летит сорок свинок - как кони - в скорости тел!

Палиндромом называется слово, которое читается одинаково в обоих направлениях. Например, слово "шалаш>" является палиндромом.

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

Будем называть слово циклическим палиндромом, если у него есть циклический сдвиг, который является палиндромом. Например, слово "масса" является циклическим палиндромом: его циклический сдвиг "самас" является палиндромом.

Вам задано слово, состоящее не более чем из \(100\) букв латинского алфавита. Требуется проверить, является ли это слово циклическим палиндромом.

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

С помощью соотношений такого типа можно задавать не только последовательности чисел, но и последовательности строк. В этой задаче рассматривается последовательность строк \(s_0, \ s_1, \ldots\) , задаваемая следующим образом.

Строка \(s_0\) пуста, а каждая строка \(s_i\) (\(i \ge 1\)) получается из \(s_{i-1}\) по следующему правилу: если десятичная запись числа \(i\) входит как подстрока в \(s_{i-1}\), то \(s_i = s_{i-1}\), иначе \(s_i\) получается приписыванием к \(s_{i-1}\) в конец десятичной записи числа \(i\).

Задано число \(n\). Необходимо найти строку \(s_n\).

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

Чтобы ничего не перепутать, мастера договорились, что Олег будет только включать лампы, а Сергей только выключать.

Театральная сцена представляет собой прямоугольник \(W\) на \(L\) метров, внутри которого расположено \(N\) ламп подсветки.

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

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

Перед началом спектакля Олег и Сергей получили подробный сценарий, в котором указано количество действий \(M\) и для каждого действия свой набор ламп подсветки, которые должны быть включены. Лампы, которые не входят в этот набор, должны быть выключены. Перед первым действием Олег должен находиться в левой части кулис, а Сергей - в правой. Изначально включены лампы, необходимые для первого действия.

Задача Олега и Сергея - организовать работу так, чтобы суммарное время всех перерывов между действиями было бы минимальным.

В 2222 году экспедиция на планету XZ-238 в звездной системе ню Малой Медведицы обнаружила в одной из пещер загадочное устройство. Вдоль стены по прямой расположены \(n\) треугольных и \(n\) круглых гнезд. Расшифровка инструкций, расположенных рядом на стене, показала, что эти гнезда следует соединить проводами: каждое треугольное гнездо должно быть соединено с каким-либо круглым, расположенным правее.

Были изготовлены \(n\) треугольных и \(n\) круглых штекеров, которые можно соединять проводами. Однако никакой маркировки нет, поэтому понять какое гнездо следует соединить с каким не удается. Начальник экспедиции хочет заказать с Земли провода. Решено было заказать один большой моток кабеля, который затем нарезать на соединительные провода. Поскольку доставка грузов с Земли дорога, необходимо заказать как можно меньше кабеля. С другой стороны, поскольку неизвестно какое гнездо требуется соединить с каким, нужно заказать такое количество кабеля, чтобы при любом способе соединения длины кабеля хватило на изготовление соединительных проводов. Помогите руководству экспедиции по заданному расположению гнезд вычислить, кабель какой длины следует заказать. Гарантируется, что хотя бы один способ соединить гнезда описанным образом существует.

Например, рассмотрим расположение гнезд, изображенное на рисунке.

Можно соединить треугольное гнездо \(1\) с круглым гнездом \(A\), а треугольное гнездо \(2\) - с круглым гнездом \(B\). Для такого соединения необходимы провода длины \(5\) и \(4\), суммарная длина - \(9\). Можно также соединить \(1\) с \(B\) и \(2\) с \(A\), в этом случае необходимы провода длины \(7\) и \(2\), суммарная длина также \(9\). Таким образом необходимо заказать с Земли кабель длиной \(9\) метров.

В случае же, показанном на следующем рисунке, есть лишь один способ соединить гнезда: \(1\) с \(A\), а \(2\) с \(B\). Гнездо \(2\) нельзя соединить с \(A\), поскольку \(A\) расположено левее. Так что в этом случае необходимо \(2\) метра кабеля.