Маленький мальчик Гриша уже сам начал делать олимпиады, и ему как раз нужно подготовить Открытую Олимпиаду по Информатике. Для олимпиады нужно придумывать задачи, а Гриша как раз очень любит этим заниматься. Каждую задачу он характеризует ее сложностью, которая является неотрицательным целым числом. Сложность олимпиады Гриша оценивает как сумму сложностей всех задач в ней.

На Открытую Олимпиаду по Информатике Грише требуется придумать $$$n$$$ задач. Конечно, Гриша еще не дорос до того, чтобы составлять олимпиаду самому, поэтому за его действиями следит многоуважаемое начальство. Начальство любит отвергать некоторые задачи, но Гриша знает, что оно не может отклонить больше, чем $$$k$$$ из его задач. Также Гриша, исходя из своего большого опыта, считает, что давать олимпиаду со сложностью меньше чем $$$x$$$ будет бессмысленно, поэтому он не допустит такого.

Как мы уже говорили, Гриша — настоящий специалист в придумывании задач и может придумать сколько угодно задач любой сложности. Он хочет придумать $$$n$$$ задач, понимая, что часть из них могут отклонить, и, конечно, он хочет, чтобы независимо от того, какие задачи его начальство отвергнет, сложность олимпиады из оставшихся задач была не меньше $$$x$$$. Конечно, Гриша является еще и лентяем, поэтому не хочет перетруждаться и планирует придумать $$$n$$$ задач с минимальной суммарной сложностью. К сожалению, сейчас он занят учебой и не может расчитать минимальную суммарную сложность этих задач. Помогите Грише, ведь до олимпиады осталось не так много времени.

Тесты к этой задаче состоят из пяти подзадач. Баллы за каждую подзадачу ставятся только при прохождении всех тестов подзадачи и всех тестов необходимых подзадач.

Алиса и Боб хотят пройти через турникет в метро. У них есть полоска, на которой в ряд написаны n строчных букв латинского алфавита. Для того, чтобы пройти через турникет, каждый должен приложить к нему бумажку с кодовым словом. Турникет сканирует слово, записанное на бумажке и открывается, позволяя пройти одному человеку. Чтобы запретить человеку ездить по одному билету несколько раз, турникет не откроется если приложить к нему бумажку со словом, которое турникет сканировал до этого.

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

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

Тесты к этой задаче состоят из пяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.

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

Чтобы пройти через турникет, надо использовать специальную карточку SLON (Subterranean Lowcost Orientational Network). У каждой карточки есть неотрицательный целый баланс — количество бурлей, которые записаны на карточке. Если на карточке есть хотя бы $$$k$$$ бурлей, то пройти через турникет возможно, после чего баланс карточки уменьшается на $$$k$$$ бурлей. Если же на карточке меньше $$$k$$$ бурлей, то Пафнутий не сможет ей воспользоваться, чтобы пройти через турникет.

Изначально у Пафнутия есть $$$n$$$ карточек, баланс карточки с номером $$$i$$$ составляет $$$a_i$$$ бурлей. Также Пафнутий накопил $$$p$$$ бурлей и может как угодно распределить эти деньги между карточками. Формально, пусть Пафнутий к балансу карточки с номером $$$i$$$ добавил $$$add_i \ge 0$$$ бурлей, тогда должно выполняться условие $$$add_1 + add_2 + \ldots + add_n \le p$$$. Возможности перераспределять деньги между карточками нет, то есть баланс карточки может увеличиваться только за счет какой-то части из этих $$$p$$$ бурлей и уменьшаться только при проходе через турникет.

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

Тесты к этой задаче состоят из пяти подзадач. Баллы за каждую подзадачу ставятся только при прохождении всех тестов подзадачи и всех тестов необходимых подзадач.

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

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

• ? l r — узнать MEX мультимножества $$$\{a_l, a_{l+1}, \ldots, a_r\}$$$
• ! i x — присвоить $$$a_i$$$ значение $$$x$$$ $$$(0 \leq x \leq n)$$$

MEX мультимножества чисел $$$\{a_1, a_2, \ldots, a_k\}$$$ — это минимальное целое $$$t \ge 0$$$ такое, что $$$t \ne a_i$$$ для всех $$$1 \leq i \leq k$$$.

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

Тесты к этой задаче состоят из тринадцати подзадач. Баллы за каждую подзадачу ставятся только при прохождении всех тестов подзадачи и всех тестов необходимых подзадач.

Филателист Петя отправился в магазин, чтобы приобрести его заветную мечту — настоящую медную монету XVII века. В магазине продавец показал Пете $$$n$$$ монет XVII века, имеющихся в наличии, каждая из которых сделана из одного из трех материалов: железа, меди или бронзы. К сожалению, время не пощадило монеты, поэтому они покрылись ржавчиной, и невозможно определить, какая монета из какого материала сделана. Чтобы Пете было проще найти нужную монету, продавец показал ему $$$m$$$ пар монет таких, что монеты из пары сделаны из различных материалов. Кроме того, продавец сказал Пете, что ровно одна из $$$n$$$ монет сделана из меди. Чтобы заполучить заветную монету, Петя решил приобрести все монеты, которые могут быть медными, исходя из информации, полученной им от продавца.

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

Определите, какие монеты купит Петя.

Тесты к этой задаче состоят из пяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.

Во Флатляндии проводится ежегодный турнир по танцам!

Из города NN приехала команда, состоящая из n танцоров, и вот настал день соревнований.

Состязания проходят в таком формате: танцоры пронумерованы от 1 до n, и изначально i-й танцор стоит на i-м месте. После этого они начинают танцевать по заранее согласованной программе выступления a: каждую минуту танцор с a_i-го места передвигается на i-е место, при этом все a_i различны. От команды требуется выстроиться так, чтобы i-й танцор оказался на b_i-м месте (аналогично, все b_i различны). После этого выступление завершается, и жюри оценивает его техничность и артистизм. При этом выступление должно продлиться хотя бы одну минуту, иначе оценивать будет просто нечего.

Но в этом году участники заподозрили жюри в подлоге: к ним пришла мысль, что, возможно, следуя программе a, они никогда не смогут занять требуемое положение b, что приводит к автоматическому поражению в турнире.

Так как они не программисты по образованию, команда города NN решила обратиться к вам за помощью: проверьте по их программе выступления a и требуемому положению b, существует ли такое положительное количество минут k, что через k минут после начала выступления i-й танцор будет находиться на b_i-м месте.

Тесты к этой задаче состоят из четырех групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.

Дана перестановка $$$a$$$ чисел от $$$1$$$ до $$$n$$$, а также набор из $$$m$$$ пар индексов. За один ход разрешается выбрать одну из этих $$$m$$$ пар и поменять элементы на соответствующих позициях местами (перестановка, соответственно, изменится). Вы можете сделать произвольное количество ходов (в частности, разрешается не делать ни одного хода).

Определим возрастающую подпоследовательность длины $$$k$$$ как набор индексов $$$j_1, j_2, \ldots, j_k$$$, для которых выполняются два условия:

• $$$1 \le j_1 \lt j_2 \lt \ldots \lt j_k \le n$$$;
• $$$a_{j_1} \lt a_{j_2} \lt \ldots \lt a_{j_k}$$$.

Какой максимально возможной длины наибольшей возрастающей подпоследовательности можно достичь при правильных обменах элементов?

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

Назовём красотой числа произведение цифр в нем. Например, красота числа 123 равняется 6, так как 1·2·3 = 6, а красота числа 209 равна 0, так как 2·0·9 = 0. По заданным числам l и r найдите максимально красивое число x такое, что l ≤ x ≤ r.

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

Решения, работающие при 1 ≤ r < 100, будут набирать не менее 10 баллов.

Решения, работающие при 1 ≤ r < 10⁶, будут набирать не менее 20 баллов.

Решения, работающие при 1 ≤ r < 10¹⁸, будут набирать не менее 40 баллов.

Решения, работающие при 1 ≤ r < 10¹⁰⁰⁰, будут набирать не менее 70 баллов.

Вам дана строка $$$s_1 s_2 \ldots s_n$$$, состоящая из $$$n$$$ маленьких английских букв. Жюри загадало перестановку $$$p_1, p_2, \ldots, p_n$$$ и получило новую строку $$$t$$$, поставив $$$i$$$-й символ строки $$$s$$$ на $$$p_i$$$-ю позицию в строке $$$t$$$. Вам необходимо найти строку $$$t$$$.

Для этого вы можете один раз задать вопрос, состоящий из $$$k$$$ выбранных вами пар индексов. Для пары индексов $$$(a_i, b_i)$$$ ($$$1 \leq i \leq k$$$, $$$1 \leq a_i \lt b_i \leq n$$$) вы узнаете, верно ли, что $$$p_{a_i} \lt p_{b_i}$$$.

Вы хотите определить искомую строку, спросив про наименьшее количество пар, то есть минимизируя значение числа $$$k$$$, при условии, что проверяющая программа является адаптивной. Это означает, что ответ к каждому тесту может быть различен в зависимости от того, про какие пары индексов вы спрашиваете. Другими словами, ваше решение должно успешно восстанавливать строку $$$t$$$ для любой возможной перестановки $$$p_1, p_2, \ldots, p_n$$$.

Сначала вам необходимо считать непустую строку $$$s$$$, состоящую из маленьких английских букв. Длина строки не превосходит $$$100$$$.

Затем вы должны вывести строку, содержащую единственное целое число $$$k$$$ ($$$0 \leq k \leq 10 ^ 4$$$), а после — $$$k$$$ строк, в $$$i$$$-й из которых будет содержаться два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \leq a_i \lt b_i \leq n$$$) — пара, про которую вы хотите спросить.

После этого, если $$$k \gt 0$$$ (то есть вы спросили про какие-то пары), вы должны считать строку, состоящую из $$$k$$$ символов, $$$i$$$-й символ которой равен «1», если $$$p_{a_i} \lt p_{b_i}$$$, и «0» в противном случае. Если ваша программа задала некорректный запрос, то вместо строки с ответами на запросы может быть задана строка «-1», если проверяющая программа жюри смогла считать и распознать ваш запрос, а затем определить его как некорректный. В случае, если ваш запрос не был распознан проверяющей системой или произошёл другой сбой, например, вы не вывели ничего или вывели слишком много чисел, вердикт проверяющий системы может быть разным.

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

Обратите внимание, после вывода ответа или в случае считывания строки «-1» вы обязательно должны сразу завершить вашу программу. В противном случае вердикт тестирующей системы может быть некорректным, в частности, вы можете получить вердикт Run-time error или Time limit exceeded!

Не забывайте сбрасывать буфер после каждого запроса. Например, на языке C++ надо использовать функцию fflush(stdout) или вызов cout.flush(), на Java вызов System.out.flush(), на Pascal flush(output) и stdout.flush() для языка Python.

Тесты к этой задаче состоят из четырёх подзадач. Баллы за каждую подзадачу ставятся только при прохождении всех тестов подзадачи и всех тестов необходимых подзадач.

Опытным участникам соревнований по спортивному программированию хорошо известна классическая задача о нахождении количества вхождений подстроки в строку. Обычно она формулируется так: дана строка-образец $$$s$$$ и строка $$$t$$$, требуется найти количество индексов, начиная с которых строка $$$s$$$ содержится в строке $$$t$$$.

К сожалению, для решения этой задачи уже придумано множество алгоритмов, поэтому сама по себе она может быть интересна только в качестве упражнения, но не олимпиадной задачи. Однако, как это часто бывает со стандартными задачами, её легко усложнить — представим, что нас интересуют не сами строки $$$s$$$ и $$$t$$$, а некоторые их подстроки $$$s[l_1 \ldots r_1]$$$ и $$$t[l_2 \ldots r_2]$$$.

Как вы уже, наверное, догадались, вам дано $$$q$$$ запросов, $$$i$$$-й из которых задаёт некоторые подстроки $$$\bar s = s[{l_1}_i \ldots {r_1}_i]$$$ и $$$\bar t = t[{l_2}_i \ldots {r_2}_i]$$$. Для каждого такого запроса необходимо посчитать количество вхождений строки $$$\bar s$$$ в строку $$$\bar t$$$.

Тесты к этой задаче состоят из четырех подзадач. Баллы за каждую подзадачу ставятся только при прохождении всех тестов подзадачи и всех тестов необходимых подзадач.