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

Например, если изначально выбрать точки $$$\{2, 4, 8\}$$$, после первого хода могут получится следующие комбинации чисел: $$$\{2, 3, 4\}$$$, $$$\{4, 5, 8\}$$$, $$$\{4, 6, 8\}$$$, $$$\{4, 7, 8\}$$$. В первом случае игра заканчивается после первого же хода, в остальных случаях можно сделать еще хотя бы один ход.

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

В данной задаче 20 тестов (помимо тестов из условия), каждый из них оценивается в 5 баллов. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.

Решения, корректно работающие при $$$1 \le a, b, c \le 100$$$, наберут не менее 15 баллов.

Решения, корректно работающие при $$$1 \le a, b, c \le 1000$$$, наберут не менее 30 баллов.

Решения, корректно работающие при $$$1 \le a, b, c \le 10^5$$$, наберут не менее 60 баллов.

Молодой и амбициозный Вано, закончивший институт год назад, наконец, решил купить квартиру в районе Ваке города Тбилиси.

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

Учитывая это, Вано хочет выбрать квартиру так, чтобы общее расстояние, которое ему придется преодолевать до всех этих зданий, было минимальным. В районе Ваке все здания описываются при помощи двух целых координат $$$(x, y)$$$ — это координаты центра здания, и размеры каждого здания составляют 1 на 1 единицу. Расстояние между двумя зданиями определяется как сумма модулей разностей их координат. Например, если одно здание расположено с координатами $$$(x_1, y_1)$$$, а другое — с координатами $$$(x_2, y_2)$$$, то расстояние между ними составляет $$$|x_1 - x_2| + |y_1 - y_2|$$$.

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

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

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

Вам даны машинки, которые есть у Феди. Он очень хочет узнать, какая самая максимальная скорость может быть у машинки, которую он уже имеет или может собрать.

В данной задаче 25 тестов (помимо тестов из условия), каждый из них оценивается в 4 балла.

Решения, корректно работающие при всех $$$a_i$$$, равных степеням двоек, наберут не менее 36 баллов.

Решения, корректно работающие при $$$1 \leq n \leq 100$$$ и $$$(\sum_{i=1}^{i \le n}{a_i}) \leq 10^5$$$, наберут не менее 52 баллов.

Берляндия и Кекляндия посылают к друг другу дипломатов с сообщениями. Чтобы никто не смог перехватить послание, они решили шифровать свои сообщения так: вместо букв они выписывают через пробел цифры номера букв в алфавите, в котором A букв, начиная с 1 в k-ичной системе исчисления (цифры каждого числа тоже через пробел). Однако, иногда по дороге цифры смазываются и нельзя понять, что там было. Однажды правительству Кекляндии пришло очередное сообщение, но в нем было очень много пропусков. На всякий случай они решили подсчитать, сколькими способами можно восстановить сообщение (составить такое сообщение, чтобы после шифровки получилась эта же последовательности цифр, не считая стертых цифр), ведь тогда будет слишком сложно понять, что хотела сообщить Берляндия. Сообщение может быть очень длинным, поэтому Кекляндия попросила вас автоматизировать этот процесс и сообщать результат по модулю $$$10^9 + 7$$$.

Помогите Кекляндии подсчитать количество способов восстановить сообщение!

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

Гиоргий Тиньковидзе, работает в Министерстве инфраструктуры Грузии (inprast'rukt'uris saminist'ro). В связи с объявленным 14-го декабря решением Европейской комиссии о предоставлении Грузии статуса кандидата на вступление в Европейский союз, министерству инфраструктуры было поручено организовать информационную поддержку празднований.

Гиоргий Подворнидзе в свою очередь требуется проложить интернет кабель через весь проспект Руставели от Площади Свободы до самого памятника Шота Руставели. Длина данного участка дороги составляет $$$k$$$ метров. В распоряжении Гиоргия есть $$$n$$$ проводов, каждый из них характеризуется длиной и порядковым номером. Гиоргию требуется составить провод достаточной длины ($$$\geq k$$$ метров), при этом получившаяся перестановка из порядковых номеров проводов должна быть лексикографически как можно меньше.

К сожалению, не все так просто, как думал Гиоргий — не любую пару проводов можно соединить между собой. Для каждого провода известны типы разъемов на его концах — либо P (папа, гр. mama), либо M (мама, гр. deda). Провода могут быть как MM, так и PP, так и MP. Соединять провода можно только через различные типы разъемов на концах. Провода можно переворачивать, а итоговый провод должен получиться с разъемом P в начале и разъемом M в конце.

Помогите Гиоргию составить нужную ему цепь из проводов или скажите, что это не возможно.