В последнее время фитнесс-клубы стали очень популярны среди жителей столицы Флатландии. В такие клубы люди ходят после работы для того, чтобы поддерживать себя в хорошей физической форме. В фитнесс-клубe "Флат" каждому из посетителей на время посещения выделяется один из \(k\) шкафчиков, в который он может убрать свои вещи на время тренировки.

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

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

В начале дня все \(k\) шкафчиков закрыты. Разумеется, персоналу клуба хочется, чтобы в конце дня также как можно больше шкафчиков были закрыты - тогда надо будет меньше работать при подготовке к очередному дню. Для того, чтобы достичь этой цели, персонал может выдавать ключи от шкафчиков посетителям произвольным образом. Например, имеет смысл выдавать ключ от открытого шкафчика тому, кто его точно закроет.

Необходимо найти максимальное число шкафчиков, которые окажутся закрытыми, в случае оптимальных действий персонала фитнесс-клуба.

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

Вот и сейчас ему поручили проверить два стоящих на расстоянии \(d\) друг от друга столба высоты \(h_1\) и \(h_2\) соответственно. Чтобы убедиться, что все хорошо, Джо должен побывать на вершинах обоих столбов.

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

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

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

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

Билетик называется счастливым, если сумма цифр на четных позициях в его номере равна сумме цифр на нечетных позициях.

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

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

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

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

Вам задано слово, состоящее не более чем из \(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\).