По рзелульаттам илссеовадний одонго анлигйсокго унвиертисета, не иеемт занчнеия, в кокам пряокде рсапожолены бкувы в солве. Галвоне, чотбы преавя и пслоендяя бквуы блыи на мсете. Осатьлыне бкувы мгоут селдовтаь в плоонм бсепордяке, все-рвано ткест чтаитсея без побрелм. Пичрионй эгото ялвятеся то, что мы чиатем не кдаужю бкуву по отдльенотси, а все солво цликеом. Вдохновившись исследованием британских учёных о восприятии человеком текста, Вася решил, что современная письменность нуждается в серьёзном упрощении. В частности, в лексиконе Васи все слова состоят только из букв \(a\), \(b\) и \(c\). Кроме того, память у Васи плохая, поэтому Вася помнит лишь слова, которые содержат не более \(L\) букв.

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

Британские учёные очень заинтересовались исследованиями Васи. Они вступили с молодым учёным в активную переписку, однако, получив очередное Васино сообщение были несколько озадачены тем, что же он имел ввиду. Так как разобраться они так и не смогли, а очередное революционное открытие уже было проанонсировано в СМИ, они решили как-то оценить уровень гениальности автора. Для этого они решили понять, а из какого минимального количества слов может состоять словарный запас Василия?

Скоро в Соединенных Штатах Берляндии пройдут выборы президента. На эту ответственную должность претендуют два кандидата: Дядя Сэм и Дядя Фродо. Вы работаете аналитиком в пред- выборном штабе Дяди Сэма, и вам поручено помочь ему победить конкурента. Раздуть газетный скандал из одержимости оппонента бросанием колец в жерла вулканов не получилось, так что придётся воспользоваться математикой.

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

Как вы знаете, Соединенные Штаты Берляндии разделены на несколько административных регионов первого уровня — штатов. Сначала в каждом из штатов проходят местные выборы, по итогам которых каждый штат отдаёт свой голос за одного из кандидатов. Если не менее половины штатов выбрало Дядю Сэма, то выигрывает он (в случае равенства голосов Дядя Сэм имеет преимущество как действующий президент), иначе побеждает Дядя Фродо. Все штаты, в свою очередь, состоят из административных регионов второго уровня, каждый из которых представлен выборщиком из административных регионов третьего уровня и так далее. Последний уровень состоит из отдельных жителей Берляндии. Всего в Берляндии \(N\) жителей и \(K\) уровней административных единиц. Одним из ключевых принципов этой страны является равенство, так что любой регион \(i\)-го уровня делится на одинаковое число регионов следущего уровня (в том числе содержит одинаковое число граждан).

Так получилось, что делением на регионы поручили заняться именно вам, то есть в ваших руках назначить, на сколько именно административных единиц \(i\)-го уровня делится (\(i−1\))-ая административная единица.

Также у вас есть сильный инструмент влияния на выбор людей — нефтяные бурли. Чтобы заставить одного избирателя отдать свой голос за Дядю Сэма, достаточно дать ему скромный подарок в размере одного нефтяного бурля.

К несчастью, изначально все \(N\) жителей Соединённых Штатов Берляндии собираются отдать свой голос за Дядю Фродо. Требуется определить минимальное количество нефтяных бурлей, которое достаточно потратить для победы на выборах.

В научно-исследовательском институте чародейства и волшебства пожар! Во время опыта Корнеева В. П. по превращению всей морской и океанской воды планеты в живую воду произошло короткое замыкание, и теперь его кабинет объят пламенем. Задача первостепенной важности — спасти из огня ценные лабораторные приборы, в особенности единственный в своём роде диван- транслятор \(µ\)-поля. Ваша задача — перенести диван-транслятор из кабинета Корнеева в запасную лабораторию изучения \(µ\)-поля.

НИИЧАВО состоит из \(N\) кабинетов, соединённых \(M\) коридорами. Кабинеты пронумерованы целыми числами от 1 до \(N\), при этом кабинет Корнеева имеет номер \(A\), а лаборатория изучения \(µ\)-поля расположена в кабинете номер \(B\). Благодаря специальному искажению пространства внутри института, все коридоры имеют одинаковую длину, которую можно пройти за 1 минуту, если двигаться быстрым шагом.

Ситуация усугубляется тем, что диван-транслятор — прибор, очень чувствительный к резким пе- репадам температуры. Внутри каждого коридора НИИЧАВО поддерживается свой температурный режим. Если абсолютная величина разности температур в двух последовательных коридорах на пути из кабинета Корнеева в лабораторию окажется больше \(D\) градусов, то диван-транслятор пе- рейдёт в нестабильное состояние, что может привести к катастрофическим последствиям. Обратите внимание, что на своём пути вы не заходите в сами кабинеты, а только переходите из коридора в коридор, поэтому климат внутри кабинетов не влияет на диван-транслятор. В силу причин магического характера, войдя в коридор, вы обязаны дойти до его конца, иными словами, останавливаться или разворачиваться посреди коридора запрещено. По каждому коридору можно перемещаться в обоих направлениях.

Определите, за какое минимальное время можно добраться из кабинета Корнеева до запасной лаборатории, не допуская резкого перепада температур. В рамках данной задачи вам предлагается ответить на поставленный вопрос для нескольких пар значений \(A\) и \(B\).

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

Вы, как коренной житель города Д. и программист по призванию, решили использовать свои профессиональные навыки на благо общества и облегчить жизнь своим соседям по улице \(М\). А именно, вы решили создать сайт, содержащий актуальную информацию о непроходимости улицы. Прежде всего, вы заметили, что улица разбита на N идущих друг за другом участков единичной длины. По странному совпадению бригада рабочих всегда выбирает для ремонта ровно один из таких участков и целиком меняет тип асфальта на нём. Затем вы пронумеровали эти участки от 1 до \(N\) и собрали информацию о типе асфальта на каждом из участков — числа \(t_1, t_2, ... , t_N\) (\(t_i\) — номер типа асфальта на \(i\)-м участке, согласно Государственному реестру дорожных покрытий). Наконец, вы определили непроходимость улицы как минимальное количество непрерывных непересекающихся отрезков c одинаковым типом асфальта, на которые она разбивается. Например, непроходимость улицы 110111 равна \(3\), потому что она состоит из трёх участков 11, 0 и 111, а идеальная улица 2222 имеет непроходимость, равную \(1\).

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