Гриша, подобно персонажу известной кинокомедии, нашел себе ночную работу в музее естественной истории. В первую же смену ему выдали его главное орудие труда — эмбоссер — и приказали провести инвентаризацию всей экспозиции.

Эмбоссер представляет собой устройство для «печати» текста на пластиковой ленте. Текст набирается последовательно, буква за буквой. В устройство входят колесо с нанесёнными по кругу строчными буквами английского алфавита, неподвижная засечка, которая указывает на текущую букву, и кнопка, печатающая выбранную букву. За одно действие можно повернуть колесо с алфавитом на одну букву влево либо вправо по циклу. Изначально засечка эмбоссера указывает на букву a. Остальные буквы расположены так, как показано на рисунке.

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

Молодой известный дизайнер Пётр решил устроить мастер-класс для широких масс. Он планирует, что на мастер-классе каждый участник создаст свой неповторимый шедевр. Пётр собирается подготовить для каждого участника огромный белый холст \(h \ см \times w \ см\) (\(h\) и \(m\) — целые числа) и баночку краски чёрного цвета, которой хватает ровно на \(s \ см^2\) холста.

Незадолго до мастер-класса Петру сообщили, что широкие массы не блещут оригинальностью, и каждый участник нарисует ровно один прямоугольник, истратив при этом целиком свою баночку краски. Более того, стороны прямоугольника обязательно будут параллельны осям холста, а расстояния от сторон прямоугольника до сторон холста будут выражаться целыми числами сантиметров. Пётр заинтересовался, сколько можно нарисовать различных произведений искусства (банальных, но всё же примечательных!) в данных условиях?

Уже начался сезон олимпиад по программированию, а значит пора писать командные тренировки. Серёжа ведёт тренировки у своих команд не первый год и знает, что к туру надо подготовить не только набор задач и разбор. Тренировка длится несколько часов, и команды, которые в ней участвуют, успевают за это время проголодаться. Поэтому на каждую тренировку Серёжа закупает некоторое количество пицц, чтобы после окончания тура команды подкрепились и обсудили свои успехи и неудачи.

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

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

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

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

Арсений уже совсем взрослый и самостоятельный. Мама решила оставить его на m дней в одиночестве и уехать отдыхать в тёплые страны. Перед этим она наготовила ему много еды, оставила достаточное количество карманных денег и постирала всю одежду.

Однако за десять минут до отъезда в тёплые страны ей пришла в голову мысль, что Арсению надо оставить точную инструкцию, какую одежду надевать в какой из дней её отсутствия. Арсений живёт в очень необычной семье, в которой вся одежда пронумерована: например, n носков Арсения имеют различными целые номера от 1 до n . Поэтому всё, что потребовалось его маме, это указать для каждого дня два числа l _i и r _i — номера носков, которые надо надеть в i -й день на левую и правую ногу соответственно (разумеется, l _i не совпадает с r _i ). Каждый носок покрашен в один из k цветов.

Уже после отъезда матери Арсений заметил, что в некоторые дни в соответствии с инструкцией ему придётся надеть носки разных цветов, что, конечно, является досадной оплошностью, вызванной спешкой перед отъездом при составлении инструкции. Но Арсений находчивый мальчик, и, по счастливому совпадению, он нашёл у себя дома банки с красками всех k цветов, которые встречаются среди его носков.

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

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

Археологи, найдя секретный ход в подземелье одной из пирамид в Цикляндии, столкнулись с необычным замком на двери в сокровищницу. На замке было написано n слов, каждое из которых состоит из нескольких иероглифов. Рядом с замком на стене был обнаружен необычный круглый рычаг, поворот которого меняет иероглифы, из которых состоят слова на замке, по некоторому принципу. Также рядом с иероглифом была найдена надпись на древнецикляндском, которая гласит, что замок откроется, только если слова, написанные на замке, станут идти в лексикографическом порядке (определение дано в пояснении).

Несмотря на то, что археологи отлично знали весь древнецикляндский алфавит, который состоял из c иероглифов, они никак не могли определить закономерность, по которой меняются буквы. Наконец кто-то догадался позвать вас, главного мыслителя современной Цикляндии. Вам хватило одного взгляда, чтобы понять, что поворот рычага на одну позицию по часовой стрелке заменяет каждый иероглиф на следующий за ним по алфавиту, то есть x -й ( 1 ≤ x ≤ c - 1 ) иероглиф превращается в ( x + 1) -й, а c -й превращается в первый.

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