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

Заклинание $$$s$$$ — это строка, состоящая из рун, длины $$$n$$$. При этом, если все подстроки заклинания длины хотя бы 2 различны, то такое заклинание называется сильным. В противном же случае, заклинание называется слабым. Например, «portal» — сильное заклинание, а «abracadabra» — слабое заклинание.

Чтобы Морти вернуться домой, ему нужно составить сильное заклинание длины $$$n$$$ — помогите ему с этим!

Подстрока строки $$$s$$$ — это последовательность символов, идущих подряд в строке $$$s$$$. Например, «abc» является подстрокой строки «dfabced».

Джерри очень хочет научиться завершать игру в гольф за два удара. Он знает, что всего есть $$$n$$$ лунок, имеющих координаты $$$(x_i, y_i)$$$.

Джерри хочет поставить шар в какую-то точку и произвести сначала удар влево, затем удар вниз, так чтобы в итоге шар оказался в какой-то лунке. Формально говоря, если Джерри изначально поставит шар в точку с координатами $$$(A, B)$$$, то затем он может выбрать любые числа $$$l, d \geq 0$$$ и двумя ударами отправить шар в точку $$$(A - l, B - d)$$$.

Однако Джерри не смог решить, в какую точку ему поставить шар. Поэтому он призвал $$$q$$$ Мисиксов, $$$i$$$-й из которых посоветовал ему поставить шар в точку $$$(a_i, b_i)$$$.

Для каждого $$$i$$$ от $$$1$$$ до $$$n$$$, помогите Джерри узнать, сможет ли он загнать шар в какую-то лунку, если последует совету $$$i$$$-го Мисикса и поставит шар в точку $$$(a_i, b_i)$$$.

Морти стоит в пещере Губителя миров, прямо перед ним очередная нейтрино бомба, сделанная Риком, и на обезвреживание осталось меньше минуты.

На экране бомбы изображены $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$. С помощью специальных кнопок на бомбе Морти может поменять местами любые два соседних числа, если их сумма нечётна. Формально говоря, Морти может выбрать любое $$$1 \leq i \lt n$$$, такое что $$$a_i + a_{i + 1}$$$ нечётно, и поменять числа $$$a_i$$$ и $$$a_{i + 1}$$$ местами. Такую операцию он может сделать сколько угодно раз.

Морти знает, что бомба будет обезврежена, если числа на экране будут идти в неубывающем порядке. Формально говоря, если $$$a_1 \leq a_2 \leq \ldots \leq a_n$$$.

Помогите Морти узнать, сможет ли он обезвредить бомбу.

У Морти завтра важная контрольная по математике, поэтому он решил не ложиться спать, пока не выучит весь материал. Для этого он приготовил себе стакан очень крепкого чая, чтобы ни в коем случае не уснуть. Однако через несколько часов Морти понял, что математика слишком скучная наука и гораздо интереснее изучать свой стакан с чаем.

Стакан представляет из себя прямоугольный параллелепипед со сторонами $$$a$$$ и $$$b$$$ сантиметров у основания и $$$c$$$ сантиметров в высоту. На внутренней части каждой грани нанесены отметки через каждый сантиметр, по которым можно узнать примерную высоту налитой жидкости (у основания отметка с числом 0, последняя отметка с числом $$$c$$$). Морти заметил, что сейчас уровень налитого им чая находится ровно на высоте $$$h$$$. Ему стало интересно, какую наименьшую отметку на стакане он сможет увидеть, наклоняя стакан так, чтобы одна сторона основания оставалась полностью на столе. При этом он не хочет пролить ни капли чая, ведь он получился очень вкусным. Также Морти знает, что если в наклоненном состоянии возле одной из граней чай будет находиться ровно на отметке, то он сможет увидеть число на ней.

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

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

Таможенник был очень уставшим и злым в конце рабочего дня, поэтому предложил Рику и Морти самую сложную задачу из своего арсенала: дана таблица $$$a$$$ из $$$n$$$ строк и $$$m$$$ столбцов, необходимо заполнить эту таблицу различными натуральными числами от $$$1$$$ до $$$n\cdot m$$$ включительно. Но такая задача оказалась слишком лёгкой для Рика, поэтому таможенник просит, чтобы выполнялись следующие утверждения ($$$a_{i, j}$$$ — число, которое находится в таблице $$$a$$$ на пересечении $$$i$$$-й строки и $$$j$$$-го столбца):

• Если мы выберем любые 2 числа $$$1 \leq i \lt j \leq n$$$, то произведения чисел в $$$i$$$-й и $$$j$$$-й строках должны являться не взаимно простыми числами (более формально — числа $$$(a_{i, 1} \cdot a_{i, 2}\cdot\ldots\cdot a_{i, m})$$$ и $$$(a_{j, 1} \cdot a_{j, 2}\cdot\ldots\cdot a_{j, m})$$$ не являются взаимно простыми для любых $$$1 \leq i \lt j \leq n$$$).
• Если мы выберем любые 2 числа $$$1 \leq i \lt j \leq m$$$, то произведения чисел в $$$i$$$-м и $$$j$$$-м столбцах должны являться не взаимно простыми числами (более формально — числа $$$(a_{1, i} \cdot a_{2, i}\cdot\ldots\cdot a_{n, i})$$$ и $$$(a_{1, j} \cdot a_{2, j}\cdot\ldots\cdot a_{n, j})$$$ не являются взаимно простыми для любых $$$1 \leq i \lt j \leq m$$$).

И тут Рик и Морти задумались: а существует ли вообще такая таблица $$$a$$$ (вдруг таможенник намеренно не хочет пускать инопланетных специалистов...)? Так как они заняты разработкой новой нейросети, то вам поручено ответить на этот вопрос. Сможете ли вы помочь Рику и Морти?

Напомним, что числа $$$a, b$$$ являются не взаимно простыми, если у них существует общий делитель, отличный от $$$1$$$.

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

У Джина есть $$$n$$$ досок с длинами $$$a_1, \ldots, a_n$$$ дюймов. За один доллар Джин может удлинить или укоротить на один дюйм любую доску по своему выбору. При этом никакая доска не должна стать короче одного дюйма.

Джин хочет получить как можно больше досок одинаковой длины, потратив не более $$$k$$$ долларов. Найдите максимальное возможное количество досок одинаковой длины, которое он сможет получить.

В одной из вселенных Рика и Морти существует огромное дерево с $$$n$$$ измерениями. Некоторые пары измерений связаны двусторонними порталами. Порталы устроены так, что для каждой пары измерений существует ровно один способ добраться от одного до другого, путешествуя по порталам. Рику нужно распределить особые межпространственные значения $$$a_1, a_2 \ldots a_{n - 1}$$$ между порталами так, чтобы минимизировать общую суммарную энергетическую стоимость перемещений между всеми парами измерений. Стоимость перемещения равна сумме всех межпространственных значений порталов, через которые надо пройти на пути из одного измерения в другое.

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

Рик и Морти летели на своей летающей тарелке в «Blitz & Chitz». Так как они задержались с одним делом, то решили полететь короткой дорогой. Как обычно бывает, они встали перед светофором, который в каждый момент времени показывает, сколько осталось секунд до переключения сигнала. Светофор попался необычно большим, он состоит из n секций, каждая из которых состоит из семи индикаторов.

Отображение цифр на 7-сегментном индикаторе

Часть индикаторов перегорела, и они не загораются на светофоре. Раз ждать еще долго, Рик решил вздремнуть. Он просыпался $$$m$$$ раз, смотрел на светофор и ложился обратно. После того как проснулся в $$$m$$$-й раз, ему стало интересно, сколько времени показывал светофор, когда они только приехали. За 1 секунду сна Рика число на светофоре уменьшалось на 1. Также Морти сообщил Рику, что все это время на светофоре горел красный цвет. Если существует несколько вариантов исходного времени, найдите минимальное возможное время.

Морти так много путешествовал с Риком, что пропустил целую четверть в школе. Пока его не было, ребята из его класса прошли факториалы. Напомним, что факториал числа $$$n$$$ обозначается как $$$n!$$$ и равен произведению первых $$$n$$$ натуральных чисел, то есть $$$n! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (n-1) \cdot n$$$.

Когда Морти пришел в класс, учитель математики дал ему интересную задачу. Он назвал число $$$k$$$ и попросил найти наибольшее натуральное число $$$n$$$, которое не больше $$$k$$$, такое, что $$$n = n!$$$.

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