Пандемия нового компьютерного вируса добралась до Байтландии. Для безопасности байтов (так зовут жителей Байтландии) школам пришлось перейти на дистанционное обучение. Знакомо, не правда ли?

Онлайн-уроки будут проходить в виде конференций, в каждой конференции может находиться максимум $$$n$$$ человек, $$$c$$$ из них обязательно преподаватели, а остальные ученики. У школы в распоряжении есть $$$k$$$ свободных конференций.

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

Поспешите, ведь начало уроков совсем скоро!

В результате оперативной работы в руки к Штирлицу попало четырёхзначное натуральное число $$$n$$$, являющееся зашифрованным кодом от сейфа Мюллера. Ещё раньше Штирлицу удалось установить, что сейф в кабинете Мюллера открывается с помощью кодового механического замка, который содержит кнопки с цифрами от $$$0$$$ до $$$9$$$. Также Штирлиц знал, что Мюллер никогда не пользовался кнопкой $$$1$$$, так как она была неисправна с момента установки сейфа.

Через некоторое время Штирлицу удалось установить используемую Мюллером методику шифрования. А именно, придумав код, Мюллер выписывал подряд цифры кода, получая при этом натуральное число, а затем умножал полученное число на каждую из его цифр.

Помогите Штирлицу разгадать код от сейфа Мюллера и овладеть секретными документами или определить, что данные, которые попали к Штирлицу, некорректны.

Всей Галактике известна Всеобъемлющая Галактическая Магистральная Сеть, соединяющая многие звёздные системы между собой. Эта транспортная сеть объединяет $$$n$$$ звёздных систем посредством $$$n-1$$$ магистралей — скоростных путей, соединяющих некоторые две звёздные системы между собой.

Главной особенностью этой магистральной сети является существование между любыми двумя звёздными системами ровно одного маршрута по этой сети.

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

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

Таким образом, Федерация решила оценить, какое максимальное количество развилок может получиться во Всеобъемлющей Галактической Магистральной Сети после добавления одной магистрали, и поручила эту задачу Вам.

Цепочка ДНК состоит из последовательности повторяющихся блоков, или нуклеотидов. Существуют четыре типа нуклеотидов, которые обозначаются латинскими буквами A, C, G, и T. Таким образом, каждая цепочка может быть схематично представлена как строка над алфавитом из этих четырех символов.

В большинстве случаев у молекулы ДНК есть две цепочки, которые комплиментарны друг другу. Для того, чтобы построить обратно-комплиментарную цепочку ДНК для заданной цепочки $$$s$$$, необходимо заменить нуклеотиды на комплиментарные, и прочитать их в обратном порядке. Комплиментарным нуклеотидом для A является T, для T — A, для C — G и для G соответственно C. Например, обратно комлиментарной цепочкой для ACG будет CGT.

ДНК-палиндромом называется цепочка ДНК, которая совпадает со своей обратно-комплиментарной цепочкой.

Для данной строки ДНК определите, является ли она ДНК-палиндромом.

На далёком-далёком континенте расположены $$$n$$$ городов. Между ними располагаются $$$m$$$ дорог: каждая соединяет два различных города и позволяет перемещаться между ними в обе стороны.

На континенте представлены три империи. Каждая империя имеет в распоряжении хотя бы один город, а каждый город принадлежит одной из империй, а именно, $$$i$$$-й город числится в составе империи $$$e_i$$$ (империи имеют номера 1,2 и 3).

Каждая империя беспокоится, что ей скоро объявит войну какая-то одна другая империя, поэтому все империи хотят расставить армейские штабы в каких-то своих городах.

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

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

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

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

Соответственно, и количество задач на таком контесте бесконечное. «Путешественники» верны своим принципам, поэтому всегда решают на четвертьфинале количество задач, равное некоторому числу Фибоначчи.

Числа Фибоначчи – это числовая последовательность, задаваемая следующими правилами:

• $$$F_0 = 0$$$
• $$$F_1 = 1$$$
• $$$F_i = F_{i - 2} + F_{i - 1}, i \geq 2$$$

На четвертьфинале 2020 «Путешественники» решили $$$F_n$$$ задач. По правилам чемпионата, они во время тура получили ровно столько же воздушных шариков, по одному за каждую задачу.

Капитан команды, Кинир, решил раздать всем трём участникам команды (включая себя) максимальное возможное равное количество шариков из имеющихся. Однако в конце обнаружилось, что осталось несколько лишних шариков.

А вот сколько именно – предстоит ответить вам.

В ряд расположены $$$n$$$ карт. У каждой карты есть сила, выраженная целым неотрицательным числом. Также существует два заклинания.

Заклинание «Равные шансы» уменьшает в два раза силу карт, у которых эта сила чётная.

Заклинание «Странное событие» уменьшает на $$$1$$$ силу всех карт, у которых эта сила нечётная.

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

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

Гипнотический велосипедный замок можно представить матрицей $$$A$$$ размера $$$n \times n$$$ ($$$n$$$ чётно), содержащей целые числа. Каждый замок разделён на $$$\frac{n}{2}$$$ прямоугольных рамочек. Более формально, рамочка с номером $$$i$$$ представляет собой числовую последовательность $$$B_i$$$, такую, что: $$$B_i$$$ = $$$ \{ A_{i, i}, A_{i, i + 1}, \ldots, A_{i, n + 1 - i}, A_{i + 1, n + 1 - i}, \ldots, A_{n + 1 - i, n + 1 - i}, A_{n + 1 - i, n - i}, \ldots, A_{n + 1 - i, i}, A_{n - i, i}, \ldots, A_{i + 1, i} \}$$$.

Для введения кода от велосипедного замка каждую рамочку можно вращать по часовой стрелке. Более формально, можно делать циклический сдвиг вправо последовательности, соответствующей нужной рамочке. Из-за таких вращений и происходит гипнотический эффект замка.

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

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

Имея два заданных замка — старый и новый — определите, эквивалентны ли они.

Антона в очередной раз пригласили принять участие в марафоне, но этот марафон оказался довольно необычным — он проводился на стадионе!

Антона позвали в другой город, поэтому про стадион, на котором он собирается бежать, ему ничего не известно (даже примерно). Чтобы скрасить свое участие в этом довольно скучном событии, он поставил перед собой задачу — узнать длину кругового участка стадиона.

Опыт Антона в забегах позволяет ему с высокой точностью отмерять расстояние и пробегать ровно $$$k$$$ метров по треку. Но памятью наш бегун похвастаться не может. Единственное, что он в силах запомнить — это сколько кругов он уже пробежал.

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

Взаимодействие происходит с помощью запросов.

Вы можете просить Антона пробежать на $$$k$$$ метров вперёд с помощью запроса «run k» ($$$1 \leq k \leq 10^9$$$). В ответ на такой запрос вы получите единственное число — количество кругов, которое он уже пробежал, включая текущий запрос. Круг считается завершённым, если бегун пробегает стартовую точку или находится в ней.

Гарантируется, что длина участка — положительное целое число, не превышающее $$$10^9$$$.

Если вы готовы указать длину кругового участка, то вы можете убедиться в его правильности с помощью запроса «ensure s». После такого запроса программа должна немедленно завершиться.

При превышении количества запросов (более 100) вы получите вердикт «Wrong answer» (при условии завершения работы программы).

Ваше решение может получить вердикт «Idleness limit exceeded», если вы ничего не выводите или забываете сбросить буфер вывода.

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

• cout.flush() или fflush(stdout) в C++;
• stdout.flush() в Python;
• flush(output) в Pascal;
• см. документацию других языков.

Дед Василий с дальней заимки, коротая долгие зимние вечера, придумал следующий пасьянс: пусть в ряд разложено $$$n$$$ карт, на каждой из которых написано по одному числу: $$$a_1, a_2, \ldots, a_n$$$. Дед Василий просматривает эти карты слева направо и некоторые из них перекладывает в правый конец ряда. Условием перемещения карты является наличие справа от неё хотя бы одной карты с большим чем у неё значением. Более строго: карта на позиции $$$i$$$ и значением $$$a_i$$$ будет перемещена вправо, если найдётся позиция $$$j \gt i$$$ такая, что $$$a_j \gt a_i$$$. Пасьянс считается законченным, когда дед Василий доходит до самой правой на данный момент карты.

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

Одним осенним вечером $$$n$$$ кальмарам из одномерного мира стала известна печальная новость: к их месту обитания приближается акула!

Акула и кальмары могут двигаться со скоростью 1 метр в секунду. При этом кальмары имеют единое сознание, поэтому в каждый момент времени двигается максимум один кальмар. Если в какой-либо момент времени акула и кальмар находятся в одной и той же позиции (их размерами можно пренебречь), то акула съедает кальмара.

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

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

Какое максимальное количество кальмаров Вы сможете гарантированно спасти, вне зависимости от действий акулы?

Матрица сравнения для двух строк $$$s$$$ и $$$t$$$ над алфавитом $$$\{A, C, G, T\}$$$ определяется следующим образом. Рассмотрим операцию: вставка в строку символа «-». Такой символ можно вставить в начало и конец строки, а также между любой парой имеющихся символов в строке. Вставим произвольное (возможно, нулевое) количество таких символов в $$$s$$$ и $$$t$$$ так, чтобы их длины стали равны. Затем запишем полученные строки в матрицу друг под другом. Например, для строк ACT и AGTT одна из возможных матриц сравнения выглядит так: $$$$$$ \begin{matrix} A & C & - & T\\ A & G & T & T \end{matrix} $$$$$$

Вес такой матрицы считается как сумма весов каждого столбца. Вес столбца определяется следующим образом: если символы в столбце совпадают и оба не равны «-», то вес равен $$$+1$$$, и $$$-1$$$ в противном случае. Не допускаются матрицы, в котором в одном и том же столбце находятся два символа «-». Например, вес матрицы, приведенной выше, равен $$$+1 -1 -1 +1 = 0$$$. Наибольший возможный вес матрицы сравнения для двух строк называется их схожестью.

Подстрокой строки $$$s = s_i, \ldots, s_{|s|}$$$ является строка $$$s_{i j} = s_i, \ldots, s_j, \, 1 \leq i \leq j \leq |s|$$$; подстрока не может быть пустой. Для данных двух строк $$$s$$$ и $$$t$$$ найдите подстроки $$$s'$$$ в строке $$$s$$$ и $$$t'$$$ в $$$t$$$ такие, что схожесть $$$s'$$$ и $$$t'$$$ максимальная среди всех подстрок $$$s$$$ и $$$t$$$.