Рудольфа отправили в командировку на другую планету на $$$10^6$$$ дней. Поэтому он снял там квартиру, которую нужно оплачивать каждый месяц. Месяц на этой планете длится $$$M$$$ дней, а оплату нужно вносить в последние $$$H$$$ дней каждого месяца. Например, если $$$M=30$$$ и $$$H=10$$$, то заплатить можно в любой день с $$$21$$$-го по $$$30$$$-е число каждого месяца включительно. Командировка начинается в первый день месяца.

Рудольф может находиться в командировке не все время, иногда он может возвращаться домой. Каждые $$$B$$$ дней Рудольф приезжает в командировку на $$$A$$$ дней. Первый его приезд приходится на $$$C$$$-й день командировки. Например, если $$$A=15$$$, $$$B=25$$$ и $$$C=10$$$, то Рудольф находится на планете с $$$10$$$-го по $$$24$$$-й день включительно, далее с $$$35$$$-го по $$$49$$$-й день и т. д. Чтобы оплатить квартиру Рудольф должен находиться в командировке.

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

Вычислите, на какой день командировки Рудольфа выселят, или определите, что он сможет прожить все $$$10^6$$$ дней.

Недавно Рудольфу подарили хитрую головоломку — кубик Рубика $$$2 \times 2 \times 2$$$.

Это устройство представляет собой куб $$$2 \times 2 \times 2$$$ с $$$24$$$-мя видимыми цветными квадратами. Грани большого куба способны вращаться вокруг трех внутренних осей куба. Каждая из шести граней состоит из четырех квадратов и окрашена в один из шести цветов: белый, оранжевый, желтый, красный, синий и зеленый.

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

Рудольф сразу же бросился изучать схемы сборки кубика. Для удобства он нарисовал его развертку и пронумеровал квадраты от $$$1$$$ до $$$24$$$, как представлено на рисунке $$$1$$$. Также он обозначил грани буквами F (фронтальная), U (верхняя), D (нижняя), L (левая), R (правая), B (задняя), как представлено на рисунке $$$2$$$. С учетом этих обозначений он стал записывать вращения граней куба двумя символами $$$SC$$$, где $$$S$$$ — одна из букв, обозначающих грань, а $$$C$$$ — число от $$$1$$$ до $$$3$$$, обозначающее количество поворотов грани по часовой стрелке. Например $$$L2$$$ будет означать поворот левой грани $$$2$$$ раза по часовой стрелке. Направление по часовой стрелке для каждой из граней представлено на рисунке $$$3$$$.

Рисунок 1. Нумерация клеток кубика	Рисунок 2. Обозначения граней

Рисунок 3. Направления вращения граней

Изучая различные схемы сборки, Рудольф наткнулся на такие понятия, как алгоритм Бога и число Бога. Он узнал, что алгоритмом Бога называют любой алгоритм, собирающий головоломку за оптимальное число ходов. А число Бога — это наибольшее количество ходов в алгоритме Бога из всех возможных начальных состояний кубика. Он узнал, что для кубика Рубика $$$2 \times 2 \times 2$$$ это число равно $$$11$$$, с учетом, что одним ходом считается поворот одной грани $$$1$$$, $$$2$$$ или $$$3$$$ раза по часовой стрелке.

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

Шутки ради Рудольфу также подарили кубик Рубика $$$1 \times 1 \times 1$$$.

Это устройство представляет собой куб $$$1 \times 1 \times 1$$$ с шестью видимыми цветными квадратами. Каждая из шести граней состоит из одного квадрата и окрашена в один из шести цветов: белый, оранжевый, желтый, красный, синий и зеленый.

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

Рудольф сразу же бросился изучать схемы сборки кубика. Для удобства он нарисовал развертку этого кубика и пронумеровал квадраты от $$$1$$$ до $$$6$$$, как представлено на рисунке $$$1$$$. Также он обозначил грани буквами F (фронтальная), U (верхняя), D (нижняя), L (левая), R (правая), B (задняя), как представлено на рисунке $$$2$$$. С учетом этих обозначений он стал записывать вращения куба двумя символами $$$SC$$$, где $$$S$$$ — одна из букв, обозначающих грань, а $$$C$$$ — число от $$$1$$$ до $$$3$$$, обозначающее количество поворотов грани по часовой стрелке. Например, $$$L2$$$ будет означать поворот левой грани $$$2$$$ раза по часовой стрелке. Направление по часовой стрелке для каждой из граней представлено на рисунке $$$3$$$.

Рисунок 1. Нумерация клеток кубика	Рисунок 2. Обозначения граней

Рисунок 3. Направления вращения граней

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

Рудольф очень любит классические алгоритмические задачи. В том числе задачу о наибольшей возрастающей подпоследовательности.

Наибольшая возрастающая подпоследовательность (НВП) массива $$$A$$$ длины $$$N$$$ — это последовательность $$$A[i_1] \lt A[i_2] \lt ... \lt A[i_k]$$$ элементов массива $$$A$$$ таких, что $$$i_1 \lt i_2 \lt ... \lt i_k$$$, $$$0 \le i_j \lt N$$$, причём $$$k$$$ — наибольшее из возможных.

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

Чтобы вам было веселее, введём ещё одно условие — перед поиском НВП порядок пар в массиве можно изменить. Очевидно, что Рудольф будет менять порядок пар так, чтобы максимизировать НВП.

Рудольф решил таки сменить сотового оператора и перейти на Минифон. Это единственный оператор, у которого можно выбрать телефонный номер любой длины, не превышающей 10³. К сожалению, длина — это единственное, что можно выбрать. Сами номера генерируются из некоторого стартового номера посредством выполнения следующей операции: i-я цифра очередного j-го номера телефона будет равна цифровому корню суммы первых i цифр (j - 1)-го номера телефона. Цифровой корень любой цифры равен этой цифре. Цифровой корень любого числа равен цифровому корню суммы его цифр. Например, цифровой корень числа 65536 равен 7, потому что 6 + 5 + 5 + 3 + 6 = 25 и 2 + 5 = 7. Стартовый номер считается первым.

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

Это интерактивная задача.

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

Чтобы Бернард не расстроился Рудольф предложил по-другому угадать номера наперстков. Он разрешил Бернарду сделать $$$50$$$ запросов вида «? L R» $$$(1 \le L \le R \le N)$$$. В ответ на каждый запрос Рудольф ответит, сколько шариков находится под наперстками в диапазоне от $$$L$$$ до $$$R$$$.

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

Чтобы сделать запрос, выведите в стандартный поток строку вида «? L R» $$$(1 \le L \le R \le N)$$$. После этого выведите перевод строки и выполните операцию $$$flush$$$.

В ответ на запрос придёт одно целое число — количество шариков в диапазоне от $$$L$$$ до $$$R$$$.

Чтобы вывести ответ на задачу, выведите в стандартный поток строку вида «! X Y», где $$$X, Y (1 \le X \lt Y \le N)$$$ — позиции наперстков, под которыми находятся шарики, и завершите программу.

Если вы сделаете более $$$50$$$ запросов вида «? L R» или сделаете некорректный запрос, решение получит вердикт «Неправильный ответ».

Если в какой-то момент ваша программа ничего не будет выводить или вы забудете выполнить операцию $$$flush$$$ после вывода вопроса или ответа, решение получит вердикт «Решение зависло».

Чтобы выполнить операцию $$$flush$$$, можете использовать (сразу после вывода запроса и перевода строки):

• cout.flush() или fflush(stdout) в C++;
• System.out.flush() в Java;
• stdout.flush() в Python;
• flush(output) в Pascal;

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

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

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

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

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

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

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

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

Однако Рудольф понял, что не всё так просто, если день рождения был 29 февраля, ибо этот день есть только в високосных годах. Високосным является год, чей номер либо делится без остатка на $$$400$$$, либо делится без остатка на $$$4$$$, но не делится на $$$100$$$. Поэтому данные люди будут праздновать день рождения далеко не каждый год.

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

Рудольф, как истинный фанат математики, приобрел необычные часы. Они имеют форму правильного N-угольника и две стрелки бесконечной длины (часовую и минутную). Часы не имеют никаких делений или надписей на циферблате. Стрелки закреплены в центре часов.

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

Помогите Рудольфу правильно определить нужные значения.

На рисунке приведен вид шестиугольных математических часов Рудольфа с наложенным для наглядности круговым циферблатом. Часы показывают время 15:40.