Рудольф собирает компьютерный класс. У него есть в наличии $$$N$$$ системных блоков и $$$M$$$ комплектующих (мониторов, клавиатур, мышек, колонок). У $$$i$$$-го системного блока есть $$$K_{i}$$$ портов определенных типов. К каждому порту можно подсоединить неограниченное количество устройств, если устройство имеет соответствующий тип подключения. Комплектующие могут быть одного из четырех видов (монитор, клавиатура, мышь, колонки) и имеют один тип подключения, то есть могут подключаться только к системным блокам, имеющим порт этого типа. Устройства, подключенные к одному системному блоку, не могут быть при этом подключены к другому системному блоку.

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

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

В конце игры вашу армию ждет штурм вражеской крепости. Для выполнения этого задания вам необходимо выстроить пирамиду из солдат вашей армии. Пирамида строится по следующему принципу. На вершине пирамиды находится некоторое количество солдат $$$P (P \ge 1)$$$. Уровнем ниже может стоять ровно на $$$X (X \ge 1)$$$ cолдата больше. Пирамида строится до тех пор, пока в армии есть солдаты. При этом значения $$$P$$$ и $$$X$$$ выбираются так, чтобы все солдаты армии были задействованы.

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

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

Одним весенним вечером Рудольф сидел и размышлял о том, кто он такой. Внезапно он понял, что он персонаж задач олимпиады «IQ ПФО».

Придя в себя спустя некоторое время Рудольф решил, что в таком случае не мешало бы украсить его комнату словами «IQ». Для этого он вырезал из бумаги $$$N$$$ палочек с длинами $$$L_i (1 \le i \le N)$$$, а также $$$M$$$ окружностей с радиусами $$$R_j (1 \le j \le M)$$$. Он решил составлять слова следующим образом: на букву «I» он потратит одну палочку, а на букву «Q» — одну палочку и одну окружность. Но не любые палочки будут гармонично смотреться с любыми окружностями. Некоторое время Рудольф составлял различные комбинации и в итоге выяснил два правила идеального слова:

1. Длина палочки для буквы «I» должна быть равна диаметру окружности для буквы «Q».
2. Длина палочки для буквы «Q» должна быть строго меньше радиуса окружности.

Идеальное слово

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

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

Помогите Рудольфу создать сильнейший меч.

Рудольф решил освежить свои познания в астрономии и скачал новейшую карту звездного неба. Он настолько увлекся ее изучением, что не заметил, как пролетело $$$12$$$ часов. За это время он умудрился запомнить абсолютно все созвездия. Для этого он воспользовался небезызвестной техникой «дворец памяти». Ну а поскольку он все же математик, то его дворец памяти представляет собой координатную плоскость. На этой плоскости Рудольф и разместил все звезды, $$$i$$$-я из которых теперь имеет координаты $$$(X_i, Y_i)$$$.

Довольный собой, Рудольф решил проверить, насколько хорошо сработала эта техника. Поздней ночью он вышел на улицу и взглянул на небо. И тут он внезапно обнаружил там кроме звезд еще и луну. Рудольф быстро понял, что далеко не все созвездия он может найти, потому что они «спрятались» за луной. Чтобы актуализировать информацию в своей голове, он решил поместить в свой координатный дворец памяти луну, которая формально представляет собой круг радиуса $$$R$$$ с центром в точке $$$(X_0,Y_0)$$$. Ну а чтобы не засорять память лишней информацией, он решил забыть координаты звезд, принадлежащих тем созвездиям, которые полностью перекрыты луной.

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

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

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

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

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

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

Выигрышная позиция	Промежуточная позиция

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

Помогите Рудольфу обыграть пчёл.

Чтобы заполнить ячейку мёдом, выведите в стандартный поток два целых числа $$$X, Y (|X, Y| \leq 10^3)$$$, где $$$X$$$ и $$$Y$$$ — координаты ячейки в заданной системе координат. Ячейка должна быть пустой перед запросом.

В ответ на этот запрос придет $$$N$$$ строк. $$$i$$$-я строка содержит два целых числа $$$X_i, Y_i (|X_i, Y_i| \leq 10^3)$$$ — координаты ячейки, которую заполняет $$$i$$$-я пчела. Гарантируется, что заполняемые ячейки перед их ходом свободны.

Когда ситуация становится выигрышной, вам на вход подаётся строка «You win!». После этого ваша программа должна завершиться. Заметьте, что ситуация может стать выигрышной как после вашего хода, так и после хода пчёл. Во втором случае строка будет подана сразу после хода, который сделал ситуацию выигрышной. Смотрите пример для лучшего понимания.

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

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

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

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

Бернард, младший брат Рудольфа, учится в школе. И недавно он познакомился с факториалами. Факториал натурального числа $$$X$$$ — это произведение всех натуральных чисел от $$$1$$$ до $$$X$$$ включительно. Факториалы так восхитили Бернарда, что он начал считать факториалы всё больших и больших чисел. В конце концов он запутался и забыл, факториал какого числа он получил.

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

Рудольф с недавнего времени решил пересмотреть свои хобби и увлекся вышиванием. Чтобы вышить очередной шедевр, Рудольфу нужно закупиться нитками. Для этого ему нужно понять, сколько вообще ниток нужно. В его распоряжении есть схема для вышивки, которая представляет собой прямоугольное поле состоящее из символов «.» и «x». Символом «x» отмечены элементы, которые как раз нужно вышивать. Рудольф уже достаточно опытен в этом деле, поэтому знает, что на один символ «x» уходит $$$L$$$ миллиметров ниток. Всем любителям вышивки хорошо известно, что в одном мотке содержится $$$K$$$ метров ниток.

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

Перед новогодними праздниками Рудольф устроился в компанию, специализирующуюся на сборке новогодних подарков из конфет. Так как до Нового Года оставалось очень мало времени, в продаже были конфеты ровно четырёх видов, имеющие стоимости $$$C_1$$$, $$$C_2$$$, $$$C_3$$$, $$$C_4$$$ рубля за одну конфету.

Рудольфу поручили обработать $$$N$$$ заявок на сборку подарочных наборов. Каждая заявка имеет следующую структуру:

1. Четыре числа $$$L_1$$$, $$$L_2$$$, $$$L_3$$$, $$$L_4$$$ — максимальное количество конфет каждого вида, которое может быть в подарочном наборе.
2. Число $$$S$$$ — суммарная стоимость конфет, которую должен иметь подарочный набор.

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

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

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

Вычислите для Рудольфа ответ на его вопрос. Так как ответ может быть очень большим, посчитайте его остаток от деления на $$$10^9 + 7$$$