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

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

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

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

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

После анализа дисков было установлено, что они использовались в XXI веке по летоисчислению, использовавшемуся древней цивилизацией — так называемому «григорианскому» календарю — год продолжительностью 365 дней, разделялся по нему на двенадцать месяцев. Второй месяц в году имел продолжительность двадцать восемь дней, первый, третий, пятый, седьмой, восьмой, десятый и двенадцатый — тридцать один день, остальные — тридцать дней. В особые года, номер которых делился на четыре и не делился на сто, либо делился на четыреста, второй месяц длился двадцать девять дней. Веком номер \(i\) назывался период с \(100 \cdot (i \ − \ 1) + 1\) года по \(100 \cdot i\).

Так как достоверно не известно, в каком порядке представители древней цивилизации записывали даты, вам, как главному специалисту по григорианскому календарю, поручили провести исследование — установить, каким датам в XXI веке могла соответствовать надпись, в предположении, что одно из чисел соответствует дню в месяце (дни в каждом месяце нумеровались с единицы), еще одно из чисел — номеру месяца (месяцы также нумеровались с единицы), и еще одно число — последним двум цифрам года в XXI веке григорианского календаря.

По заданной надписи на диске выясните, каким датам в XXI веке она могла соответствовать.

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

После долгих прений жюри утвердило регламент проведения соревнований. Соревнования длятся \(m\) дней. Всем участникам выдаются одинаковые грядки с \(n\) ростками бамбука. В момент начала соревнований — 5:00 первого дня — высота \(i\)-го ростка на грядке каждого участника равна \(a_i\) . Каждую полночь \(i\)-й росток вырастает на \(b_i\) . Утром каждого дня, начиная с первого, ровно в 6:00, каждый участник может один раз постричь бамбук на своей грядке. Происходит это так: участник выбирает \(i\) и \(j\) \((1 \le i \le j \le n)\) — левую и правую границу отрезка ростков, которые он хочет постричь, затем выбирает высоту \(l \ (0 \le l \le 2 \cdot 10^9\) ), и все ростки, с \(i\)-го по \(j\)-й включительно, высота которых больше \(l\), обрезаются до высоты \(l\). Сравнение работ происходит в полдень \(m\)-го дня. Победителями соревнований считаются те участники, которые, сделав минимальное количество стрижек, смогли получить грядку, все \(n\) ростков на которой имеют высоту \(h\).

Теперь жюри интересно, какое минимальное число раз победителю придется стричь бамбук.

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

Обычно внизу каждой страницы условий есть надпись вида «Страница \(i\) из \(n\)», где \(i\) — номер страницы условий, а \(n\) — количество страниц в условиях. Однако на этом листе была всего одна длинная последовательность цифр. Видимо, принтер почему-то не напечатал ни одного символа кроме цифр. Таким образом, номера \(i\) и \(n\) слились в единую последовательность цифр.

Теперь понять, какой же был номер у найденной страницы, стало большой проблемой, и решений у этой задачи может быть много. Роботу стало интересно, сколько существует решений, но так как робот не предназначен для решения таких задач, он нуждается в вашей помощи. Страницы в условиях нумеруются от \(1\) до \(n\), числа \(i\) и \(n\) записываются без ведущих нулей.

Выясните, сколько есть корректных надписей вида «Страница \(i\) из \(n\)», при удалении из которых всех символов кроме цифр получается заданная во входном файле строка

Многим из вас, наверное, известна легенда про Ханойскую башню. Легенда гласит, что в одном далеком монастыре находится бронзовый диск, на котором закреплены три алмазных стержня. Давным-давно, в самом начале времен, монахи этого монастыря провинились перед богами. Разгневанные боги положили \(n\) дисков на один из стержней, все диски имели разные радиусы и были расположены по убыванию радиуса — самый большой диск лежал снизу, на нем диск поменьше, \(\dots\) , самый маленький диск располагался сверху. Монахи должны перекладывать диски между стержнями, причем каждый раз должны класть диск либо на пустой стержень, либо поверх большего диска. Как только все \(n\) дисков будут переложены со стержня, на который боги сложили их, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.

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

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

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