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

Система Интернет-банкинга Bank 2.0, используемая одним Очень Крупным Банком, использует следующий способ ввода пароля. Серверной частью системы случайно генерируются \(n\) строк \(s_1, \ldots, s_n\), каждая из которых состоит из \(m\) строчных букв латинского алфавита (предполагается, что пароли состоят только из таких букв).

При вводе пароля пользователю разрешается выполнять такую операцию: выбрать из данных строк две
(обозначим их как \(s_i\) и \(s_j\), \(1 \le i, j \le n\), \(i \ne j\)) и некоторую позицию \(k\) (\(1 \le k \le m\)) в них, после чего поменять местами \(k\)-е символы в \(s_i\) и \(s_j\). Например, если \(s_i="abcde"\), \(s_j="vwxyz"\), \(k=3\), то после выполнения этой операции будут верны следующие равенства: \(s_i="abxde"\) и \(s_j="vwcyz"\). Для ввода пароля пользователю необходимо за минимальное число таких операций добиться состояния, в котором хотя бы одна из строк \(s_1, \ldots, s_n\) совпадает с \(p\).

Ваша задача состоит в том, чтобы написать программу, которая по заданному набору строк \(s_1, \ldots, s_n\) и паролю пользователя \(p\) определит минимальное число операций указанного типа, которые необходимо выполнить для ввода пароля, а также найдет способ ввода пароля за такое число операций.

Приехав в Хоббитанию, белый маг Гэндальф принялся рассказывать Бильбо последние новости из Средиземья. Больше всего впечатлительного хоббита поразил рассказ о Большом огромном коллайдере - только представить себе гигантских размеров кольцо, зарытое под землей!

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

Бильбо хочет прокопать новые коридоры в норе, но так как копать будут только Фродо и сам Бильбо (не Гэндальф же!) , есть возможность прокопать только один или два новых коридора.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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