Вы являетесь организатором крупного турнира, в котором будут участвовать $$$k$$$ атлетов. У вас есть $$$n$$$ знакомых атлетов, часть из которых вы хотите пригласить на турнир. Про $$$i$$$-го атлета вам известны его сила и выносливость — целые числа $$$p_i$$$ и $$$s_i$$$ соответственно. Атлет $$$j$$$ гарантированно побеждает атлета $$$i$$$ только если он строго сильнее и выносливее его, то есть, если $$$p_j \gt p_i$$$ и $$$s_j \gt s_i$$$ одновременно выполнены. В противном случае победить может любой из них.

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

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

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

Это интерактивная задача. Не забывайте, что ваша программа должна каждый раз после вывода сбрасывать буфер вывода. Для сброса буфера вывода можно использовать fflush(stdout) в C++, system.out.flush() в Java, stdout.flush() в Python. Если вы используете другой язык программирования, посмотрите в его документации, как выполняется эта операция.

Вася утверждает, что он изобрел алгоритм сортировки $$$n$$$-элементного массива $$$a$$$ (в котором все элементы различны), который делает меньше, чем $$$\lceil \log_2 (n!)\rceil$$$ сравнений!

Вася задаст вам не более $$$\lceil \log_2 (n!)\rceil - 1$$$ запросов вида: сравнить элементы $$$a_i$$$ и $$$a_j$$$. Вася утверждает, что данных запросов достаточно, чтобы отсортировать массив $$$a$$$, то есть, чтобы однозначно определить перестановку позиций массива $$$a$$$ от меньшего элемента к большему: $$$\operatorname{ord}_1, \operatorname{ord}_2, \dots, \operatorname{ord}_n$$$.

Ваша задача — найти перестановку позиций, отличающуюся от перестановки Васи, которая также согласуется со всеми запросами Васи.

Изначально программа жюри отправит одно целое число $$$n$$$ ($$$3 \le n \le 18$$$) — размер массива.

Далее программа жюри отправит не более $$$\lceil \log_2 (n!)\rceil - 1$$$ запросов в следующем формате:

• $$$?$$$ $$$i$$$ $$$j$$$ — сравнить $$$a_i$$$ и $$$a_j$$$ ($$$1 \le i, j \le n$$$; $$$i \ne j$$$).

На каждый запрос жюри ваша программа должна вывести <, если $$$a_i \lt a_j$$$, и > в противном случае.

После этого программа жюри отправит свой ответ в следующем формате:

• $$$!$$$ $$$\operatorname{ord}_1 \operatorname{ord}_2 \dots \operatorname{ord}_n$$$

В ответ на это ваша программа должна вывести перестановку, отличную от перестановки жюри, которая согласуется со всеми предыдущими запросами, в аналогичном формате. Если возможных перестановок несколько, выведите любую из них. Обратите внимание, что массив $$$a$$$ выводить не нужно!

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

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

Не забывайте сбрасывать буфер вывода каждый раз, когда что-то выводите!

В городе NN закончилось строительство кафе для мафии. Столики в этом кафе одноместные и пронумерованы числами от $$$1$$$ до $$$n$$$ в порядке привлекательности, где столик $$$1$$$ является самым привлекательным, а столик $$$n$$$ — самым непривлекательным. Для удобства также пронумеруем членов мафии числами от $$$1$$$ до $$$n$$$ в порядке их значимости, так что номер $$$1$$$ — это самый значимый босс мафии, а номер $$$n$$$ — самый незначительный новобранец.

Мафиози — очень занятые люди, и у $$$i$$$-го из них есть лишь один временной промежуток в расписании, когда он может посетить кафе — с момента времени $$$a_i$$$ до момента времени $$$b_i$$$ включительно, и он хочет провести в кафе всё это время.

Администратор кафе планирует рассадку людей за столики, стараясь самым значимым членам мафии отдать самые привлекательные столики. Мафиози номер $$$1$$$ он посадит за стол номер $$$1$$$, тем самым заняв этот стол в промежуток времени с $$$a_1$$$ до $$$b_1$$$. Мафиози номер $$$2$$$ он попробует также посадить за стол номер $$$1$$$, но если отрезки $$$[a_1, b_1]$$$ и $$$[a_2, b_2]$$$ пересекаются, то сделать это не получится, и мафиози номер $$$2$$$ достанется стол номер $$$2$$$.

Таким образом, мафиози номер $$$i$$$ назначают столик сразу после мафиози номер $$$i-1$$$. Из всех свободных (в промежуток времени с $$$a_i$$$ до $$$b_i$$$) столиков мафиози номер $$$i$$$ посадят за столик с наименьшим номером. Обратите внимание, что обе границы отрезка включены в него, то есть, если для каких-то двух различных мафиози $$$i$$$ и $$$j$$$ верно, что $$$b_i = a_j$$$, то им обязательно должны достаться разные столики.

Помогите администратору составить рассадку.

Дан массив целых чисел $$$a_1, a_2, \dots, a_n$$$, все числа в массиве от $$$1$$$ до $$$m$$$.

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

Дан связный неориентированный граф, состоящий из $$$n$$$ вершин и $$$m$$$ ребер. В графе отсутствуют петли и кратные рёбра. Найдите в этом графе любой путь $$$P$$$ между заданными вершинами $$$s$$$ и $$$t$$$ такой, что:

1. $$$P$$$ не содержит никакую вершину графа дважды;
2. $$$P$$$ содержит строго больше вершин, чем кратчайший путь между $$$s$$$ и $$$t$$$;
3. $$$P$$$ содержит наименьшее число вершин среди всех путей, удовлетворяющих условиям $$$1$$$ и $$$2$$$.

Дан неориентированный граф, состоящий из $$$n$$$ вершин и $$$m$$$ рёбер. В графе отсутствуют петли и кратные рёбра. Не гарантируется, что данный граф — связный.

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

Ваша задача — определить, можно ли удалить не более $$$k$$$ рёбер таким образом, чтобы получившийся граф стал двудольным.