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

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

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

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

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

К сожалению, Codegram пока ещё недостаточно надежен — при передаче сообщений возможны ошибки: в некоторых словах иногда пропадают отдельные буквы. Хорошо, что в каждом слове может пропасть не более одной буквы! Например, слово codecup при передаче может быть искажено на codecp или на codcup, но не может быть искажено на codecap (одна из букву изменилась на другую) или cdecp (две буквы пропали).

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

Рудольф тренируется решать задачи на популярном сайте CodeForSquares. Бернард следит за Рудольфом, чтобы тот тренировался достаточно усердно.

Чтобы убедить Бернарда, Рудольф показывает статистику решенных задач. Статистика выглядит следующим образом. Есть картинка, где каждому дню соответствует небольшой квадратик изначально белого цвета. При решении задач в этот день соответствующий квадратик начинает перекрашиваться в зеленый цвет. Квадратик будет полностью закрашен, если Рудольф решит хотя бы $$$3$$$ задачи в этот день. Такой день назовем 'успешным' (любое промежуточное состояние все равно не устроит Бернарда).

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

Кондитерская «Слойки на вынос» всегда имеет большое количество заказов. Для изготовления слоек используется Автоматическая Машина Выпечки Х (АМВ Х), которая может изготовить одну слойку за $$$t_0$$$ минут.

Со временем машина стала барахлить и теперь может изготовить подряд только $$$b$$$ слоек, после чего должна «отдохнуть» $$$k$$$ минут. После «отдыха» машина может снова испечь до $$$b$$$ слоек, потом ей надо снова «отдохнуть» и т.д.

Чтобы не терять клиентуру из-за невозможности выполнить заказы в срок, хозяйка кондитерской, Ванесса, приобрела $$$n$$$ новых Автоматических Машин Выпечки ХХ (АМВ ХХ), которые могут работать круглосуточно без перерыва. $$$i$$$-я новая машина может изготовлять одну слойку за $$$t_i$$$ минут. Все машины могут работать одновременно.

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

Рудольф последнее время сильно занят и делегирует просьбу Ванессы вам.

Дано $$$s$$$  — количество слоек в заказе. Ванесса и Рудольф хотят знать, за какое минимальное время можно выполнить заказ, используя все или некоторые, имеющиеся в распоряжении, Автоматические Машины Выпечки?

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

Всего у него на полке имеется $$$n$$$ ингредиентов, расположенных в ряд. Рудольф, применив свои математические способности, рассчитал, что вкусность $$$i$$$-го ингредиента равна $$$a_i$$$. Исходя из этого, он определяет вкусность коктейля как побитовое исключающее ИЛИ вкусностей входящих в него ингредиентов.

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

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

На любимом поле Байера есть $$$n$$$ нор (пронумерованных с 1 до $$$n$$$), соединенных между собой туннелями. Некоторые норы имеют выход на поверхность (назовём такие норы входами/выходами), в другие же норы можно попасть только по туннелям. Из каждой норы можно попасть в любую другую нору и только одним путем. Входами/выходами являются норы, из которых ведёт только один туннель.

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

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

Рудольф знает, сколько мячей лежит в каждой из нор. Ему стало интересно, каково математическое ожидание числа мячиков, собранных Байером, если он начнёт путь от норы с номером $$$s$$$.

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

Ход в онлайн-шахматах состоит из трёх этапов:

1. игрок выбирает фигуру, которой будет ходить;
2. приложение подсвечивает клетки доски, на которые можно поставить фигуру, в том числе — съесть фигуру соперника;
3. игрок выбирает одну из подсвеченных клеток и делает ход выбранной фигурой в эту клетку.

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

Необходимо учитывать следующее:

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

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

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

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

Таким образом, за один запрос Рудольф может назвать два числа $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq n$$$), а Бернард покажет, сколько различных символов содержится в позициях от $$$l$$$ до $$$r$$$ загаданной строки. Когда Рудольф посчитает, что знает достаточно информации о загаданной строке, он должен назвать, сколько различных подстрок содержит эта строка.

Помогите Рудольфу правильно посчитать количество различных подстрок не более чем за $$$32768$$$ запросов.

Можно сделать не более $$$32768$$$ запросов о количестве различных символов на подстроке. Каждый запрос должен иметь вид '? l r', где $$$l$$$ и $$$r$$$ — индексы исходной строки, между которыми (включительно) считается количество различных символов. Должно выполняться условие $$$1 \leq l \leq r \leq n$$$.

На каждый такой запрос будет выведено одно число $$$k$$$ — количество различных символов в подстроке, $$$1 \leq k \leq r-l+1$$$.

Ответ должен быть выведен в формате '! m', где $$$m$$$ — количество различных подстрок загаданной строки. Этот ответ не учитывается в общем количестве запросов, то есть его можно вывести даже после $$$32768$$$ запросов, указанных выше.

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

Интерактор не является адаптивным, то есть загаданная строка не меняется по мере поступления запросов.

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

На следующий день, пока Рудольф был на работе, Байер нашел этот массив. Как любой уважающий себя пёсик он его съел. Придя домой, Рудольф понял в чем дело и сильно расстроился. Но позже вспомнил, что у него осталось $$$m$$$ записей про отрезки массива вида $$$l, r, s$$$, где $$$l$$$ и $$$r$$$ — границы отрезка, а $$$s$$$ — сумма элементов на нем. Поскольку Рудольф был уставший прошлым вечером, отрезки, на которых он считал сумму, были длиной не более 10.

Рудольф попросил вас помочь ему восстановить любой подходящий массив. Гарантируется, что ответ существует.

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

Опечаленный, он шёл, рассматривая столбы из еловых брёвен, которые стояли вдоль дороги. Всего Рудольф насчитал $$$n$$$ столбов, которые имели высоты $$$h_1, h_2, \ldots h_n$$$ и стояли в точках с координатами $$$x_1, x_2, \ldots x_n$$$.

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

Рудольф может выбрать $$$a$$$-й и $$$b$$$-й столбы и толкнуть $$$a$$$-й в сторону $$$b$$$-го. Если $$$a$$$-й столб упадёт на вершину $$$b$$$-го (другие столбы не являются помехой — ведь Рудольф может заранее срубить их в сторону), то $$$b$$$-й столб, дорога и нижняя часть $$$a$$$-го столба образуют портал в форме прямоугольного треугольника. Помогите Рудольфу выбрать столбы так, чтобы максимизировать площадь портала и привезти из Рамени как можно больше мороженого.