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

Рудольфу доступны следующие команды:

• удалить символ из начала или с конца строки, данная команда занимает $$$2$$$ единицы времени;
• добавить символ в начало или в конец строки, данная команда занимает $$$2$$$ единицы времени;
• заменить любой символ строки на противоположный (например, «a» на «z», «b» на «y» и так далее), данная команда занимает $$$1$$$ единицу времени.

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

Рудольф попал в противоположное измерение, где всегда светло, а вместо лампочек используют генераторы тьмы, расположенные на огромной прямоугольной площадке, представляющей собой клетчатое поле. Каждый генератор характеризуется координатами клетки ($$$X_i$$$, $$$Y_i$$$), в которой он расположен, и мощностью $$$D_i$$$. В клетке ($$$X_i$$$, $$$Y_i$$$) генератор создает тьму, равную $$$D_i$$$; в клетках вокруг генератора (в восьми соседних клетках; клетка является соседней, если граничит с текущей по стороне или по углу), создается тьма равная $$$D_i-1$$$, в клетках вокруг этих клеток тьма равна $$$D_i-2$$$ и так далее, пока тьма не достигнет нуля (смотрите пример в примечании). Если на какую-то клетку воздействуют нескольких генераторов, то их тьма складывается.

Рудольф хотел отдохнуть в тени, но внезапно обнаружил, что в этом измерении он существует сразу в форме $$$M$$$ тёмных Рудольфов. Каждый из них имеет порог тьмы, при котором он может существовать. То есть каждому Рудольфу нужно находиться в клетке, в которой тьма не меньше определённого значения. В каждой клетке может находиться только один тёмный Рудольф. Помогите Рудольфу разместить свои сущности либо выясните, что это невозможно.

Рудольф решил заняться своим здоровьем. Он прочитал, что ходьба очень полезна, и купил фитнес-браслет, чтобы отслеживать свои успехи. В течение $$$N$$$ дней браслет считал, сколько шагов $$$S_i$$$ за $$$i$$$-й день сделал Рудольф.

Через некоторое время ему захотелось визуализировать свой прогресс, и он расположил на координатной плоскости точки $$$(i, S_i)$$$. Взглянув на получившийся график, Рудольф понял, что отдельно взятые точки не очень репрезентативны. Тогда он решил построить прямую по следующим правилам. Для прямой $$$F(X) = AX + B$$$ он ввёл величину ошибки $$$E = \sum\limits_{i=1}^N{(S_i - F(i)) ^ 2}$$$. Очевидно, чем меньше величина ошибки, тем правильнее прямая покажет прогресс Рудольфа. Но порой точки так сильно отличались, что даже оптимальная прямая казалась ему недостаточно удачной. Тогда Рудольф подумал, почему бы не построить несколько прямых. Он решил разбить весь массив имеющихся у него измерений на несколько непрерывных и непересекающихся частей, для каждой из них построить прямую и посчитать суммарную ошибку. Но чтобы не дробить массив слишком сильно, Рудольф ввёл дополнительный штраф $$$C$$$ за каждую отдельную часть. Он получил следующую формулу ошибки для своей системы оценки успехов: $$$M \cdot C + \sum\limits_{i=1}^M{E_i}$$$, где $$$M$$$ — количество частей, на которые разбит массив данных, а $$$E_i$$$ — величина ошибки $$$i$$$-й части. Такая формула полностью устроила Рудольфа. Но минимизировать эту ошибку оказалось непростой задачей, поэтому он просит вас помочь ему с этим.

Рудольф купил себе новую машину Presla Model Z и хочет испытать её на тестовом полигоне.

Новая машина — очередной хит X Æ A-12 Маска, сына того самого Илона. Её характеристики бесподобны. Максимальная скорость безгранична, а потребление электроэнергии минимально. К тому же, новые электродвигатели позволяют получать одинаковый разгон независимо от скорости. Новая модель способна разгоняться с ускорением $$$accel$$$ км$$$/c^2$$$, при этом энергозатраты равны $$$F_a$$$ единиц за одну секунду ускорения. Тормозная система данной модели позволяет мгновенно сбрасывать скорость до любого значения, при этом пассажиры совсем не почувствуют этого из-за системы UGSDS (Ultra Giga Soft Driver Supporting). Это новая адаптивная система поддержки четвертой, пятой и других точек тела человека в кресле. Для экономии заряда батарей используется рекуперативная система Eco Super Power, которая позволяет заряжать батареи, пока машина едет на большой скорости. Данная система позволяет поддерживать любую скорость за $$$F_v$$$ единиц заряда в секунду.

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

На текущем рабочем месте Рудольф получает $$$P_t$$$ рублей за одну рабочую секунду. Клубная карта сети зарядок БерЭлектроНефть позволяет заряжаться по низкой цене в $$$P_f$$$ рублей за одну единицу заряда.

Рудольф знает длину своего любимого маршрута, и он хочет знать, как много денег он может потерять при поездке по этому маршруту.

Рудольф купил себе новую машину Presla Model Z и хочет испытать её на тестовом полигоне.

Новая машина — очередной хит X Æ A-12 Маска, сына того самого Илона. Её характеристики бесподобны. Максимальная скорость безгранична, а потребление электроэнергии минимально. К тому же, новые электродвигатели позволяют получать одинаковый разгон независимо от скорости. Новая модель способна разгоняться с ускорением $$$accel$$$ км$$$/c^2$$$, при этом энергозатраты равны $$$F_a$$$ единиц за 1 секунду ускорения. Тормозная система данной модели позволяет мгновенно сбрасывать скорость до любого значения, при этом пассажиры совсем не почувствуют этого из-за системы UGSDS (Ultra Giga Soft Driver Supporting). Это новая адаптивная система поддержки четвертой, пятой и других точек тела человека в кресле. Для экономии заряда батарей используется рекуперативная система Eco Super Power, которая позволяет заряжать батареи, пока машина едет на большой скорости. Данная система позволяет поддерживать любую скорость за $$$F_v$$$ единиц заряда в секунду.

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

На текущем рабочем месте Рудольф получает $$$P_t$$$ рублей за одну рабочую секунду. Клубная карта сети зарядок БерЭлектроНефть позволяет заряжаться по низкой цене в $$$P_f$$$ рублей за один ватт.

Рудольф знает длину своего любимого маршрута, и он хочет знать, как много денег он может потерять при поездке по этому маршруту.

Он уже протестировал данный маршрут на тестовом полигоне, а теперь хочет воплотить полученные стратегии на реальных дорогах. Вот только на реальных дорогах бывают и другие участники движения. Но, благодаря системе «ГлаВаш» он частично может решить эту проблему. Он выезжает только в том случае, когда на его пути есть всего одна машина — машина его коллеги по работе. Его коллега также нашел для себя оптимальную стратегию движения. Стоит заметить, что обе машины выезжают в одну сторону, но с разных стартовых точек. Начальная скорость каждой машины равна нулю.

Реальные дороги накладывают реальные ограничения на движение. Например, существуют очень строгие правила обгона — обгон возможен только в том случае, если скорость обгоняющей машины не менее, чем на $$$30\%$$$ выше скорости обгоняемой машины. В противном случае обгоняющей машине придется сбросить скорость и ехать за впереди идущей машиной.

Рудольф хочет поразить Байера своими магическими способностями. Чтобы это сделать, он покажет ему фокус. Для фокуса он возьмёт колоду из N различных карт, тщательно и равномерно перемешает её и положит перед собой рубашкой вверх. Затем он попытается угадать верхнюю карту. Если это удалось, все ликуют, и фокус завершается. Иначе он запоминает карту, откладывает её и продолжает угадывать верхнюю карту в оставшейся колоде. К сожалению магии не существует, поэтому Рудольф просит вас посчитать математическое ожидание количества попыток, через которое он угадает карту.

Путешествия Рудольфа по параллельным мирам привели к ожидаемому результату, он встретил альтернативного Рудольфа. Теперь Рудольф пытается понять, что у него общего с альтернативным Рудольфом.

Рудольф характеризуется последовательностью из $$$N$$$ целых чисел $$$A_i$$$. Альтернативный Рудольф — последовательностью из $$$M$$$ целых чисел $$$B_i$$$. Общими характеристиками Рудольфов являются такие целые числа, которые входят и в характеристики основного Рудольфа, и в характеристики альтернативного Рудольфа, причём в том же порядке. Более того, так как Рудольфы перфекционисты, числа в выбранных характеристиках должны строго возрастать. Ну и очевидно, что из всех подходящих наборов нужно выбрать наидлиннейший.

Пока Рудольфы общаются между собой и смотрят детские фотографии, определите, что общего между двумя Рудольфами.

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

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

Рудольфа мучали две мысли:

1. После выполнения $$$M$$$ разрезов получилась какая-то фигура. Какой же она площади?
2. Зачем Рудольф так сильно изрезал листок?

Если второй вопрос скорее риторический, то первый вопрос стал для Рудольфа критически важным. Известно, что изначально у Рудольфа был лист бумаги, который помещался в резак. Лист бумаги имел форму произвольного многоугольника без самопересечений. Рудольф запомнил, какие координаты на координатной плоскости резака соответствовали вершинам многоугольника, описывающего лист бумаги, и по каким линиям он делал разрез. Стоит заметить, что после выполнения каждого разреза Рудольф убирал некоторые отрезанные части.

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

Рудольф — большой фанат Леонардо да Винчи. Леонардо да Винчи оставил огромное наследие, намного опередившее его время. Свои записи гений оставлял в оригинальной технике, которую решил изучить и исследовать Рудольф. Он выяснил, что великий Леонардо представлял числа в «зеркальной» двоичной записи, переводя затем обратно в десятичную систему.

Рудольф хочет дешифровать все имеющиеся у него записи Леонардо и просит вас помочь ему, а именно, написать программу, которая выводит число, двоичная запись которого выглядит зеркальным отражением двоичной записи заданного числа.

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

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

Помогите Рудольфу это сделать.