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

Процесс дележа урожая проходит следующим образом:

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

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

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

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