Зельда опять бродит по подземельям, и ей очень хочется победить всех боссов, которые в них прячутся. Однако не всех боссов Зельда способна победить сразу, поэтому она тщательно выбирает, с кем ей сразиться сначала.
Иерархия боссов представляет собой подвешенное дерево, где вершины — это боссы, а рёбра — отношения начальник/подчиненный между боссами. Если в дереве вершина $$$v$$$ является ребенком вершины $$$u$$$, то босс с номером $$$u$$$ — непосредственный начальник босса с номером $$$v$$$. Будем называть непосредственного начальника лордом, а непосредственного подчиненного — слугой.
Зельда придерживается следующей стратегии:
- Она выбирает таких $$$u$$$ и $$$v$$$, что $$$v$$$ — единственный слуга босса $$$u$$$.
- Затем она расправляется с боссом $$$v$$$.
- После этого все слуги босса $$$v$$$ переходят в подчинение $$$u$$$.
- Процесс повторяется.
Однако боссам не нравится, что после такого действия некоторым из начальников приходится перерабатывать, так как появляется слишком много слуг. Для того чтобы оптимизировать нагрузку, структура боссов перестраивается:
- Выбирается босс $$$w$$$ с самым большим числом слуг (если таких несколько, то имеющий максимальный номер из них).
- Выбирается его слуга $$$y$$$ с наибольшим номером.
- $$$y$$$ становится лордом всех остальных слуг $$$w$$$.
- $$$y$$$ при этом остается слугой $$$w$$$.
После этого Зельда снова ищет боссов, у которых ровно один подчиненный, и побеждает их, затем иерархия боссов снова перестраивается, и так до тех пор, пока Зельда может найти, кого ей победить. Помогите Зельде понять, сколько боссов останется после всех ее побед.
В первой строке дано целое число $$$n$$$ — число боссов ($$$1 \le n \le 10^5$$$).
Далее дано $$$n$$$ строк, описывающих слуг боссов. Строка с номером $$$i$$$ состоит из числа $$$k_i$$$ (числа слуг босса номер $$$i$$$) и следующих за ним $$$k_i$$$ различных целых чисел $$$s_1, \ldots, s_{k_i}$$$ — номеров этих слуг ($$$1 \le s_{j} \le s_n$$$, $$$s_j \ne i$$$).
Гарантируется, что описанная структура задает подвешенное дерево.
В первой строке выведите $$$m$$$ — число боссов, которые не будут побеждены Зельдой. Во второй строке через пробел выведите $$$m$$$ чисел — номера боссов, которых Зельде не удастся победить.
42 2 301 40
1 1
There are summons, each with their own name, and spells to summon them. It is well-known that summons are quite picky and only respond to spells that are prefixes of their names.
You contracted a total of $$$n$$$ summons, the $$$i$$$-th of which has the name $$$s_i$$$; and there are $$$m$$$ magical spells in your spell book, the $$$i$$$-th of which is $$$t_i$$$. A new revolutionary casting technique allows you to summon two summons $$$i$$$ and $$$j$$$ with one spell $$$k$$$ if all of the following is true:
- $$$t_k$$$ is a prefix of $$$s_i$$$;
- $$$t_k$$$ is a prefix of $$$s_j$$$;
- there exists no string longer than $$$t_k$$$ that is also a prefix of both $$$s_i$$$ and $$$s_j$$$.
Before the final fight with a big evil boss you want to determine how many pairs of summons can be summoned with a single spell. Note that one spell may fit the description for more than one pair of summons; in this case all of such pairs should be counted in the answer.
The first line of input contains two integers $$$n$$$ and $$$m$$$ — the number of summons and spells respectively ($$$1 \le n, m \le 2 \cdot 10^5$$$).
In the $$$i$$$-th of the following $$$n$$$ lines, the name of the $$$i$$$-th summon is given as a string of lowercase Latin letters (from 'a' to 'z').
In the $$$j$$$-th of the following $$$m$$$ lines, the $$$j$$$-th spell is given — also a string of lowercase Latin letters.
The total length of strings from one set does not exceed $$$10^6$$$.
Output a single integer: the number of pairs of summons that can be summoned with a single spell in your spellbook.
3 4abacabaababbbbaabababacaba
1
You and your friend are visiting Grand Canyon but you've split several minutes ago and now can't find each other.
Thankfully, you still have your cell phones but the mobile service connection is awful. So the only thing you can do is to check whether your friend is within a distance of no more than $$$2d$$$ from you. Problem is: the value of $$$d$$$ is unknown since there is no app on the phone to calculate it. You only know that $$$d$$$ is an integer in the range from $$$1$$$ to $$$10^5$$$.
Currently, you are at point with coordinates $$$(0, 0)$$$ and it's known that
- your friend is too scared to be alone so he doesn't move and stays at currently unknown point $$$(x_0, y_0)$$$ with possibly non-integer coordinates, where $$$-10^5 \le x_0, y_0 \le 10^5$$$;
- your friend couldn't have been left behind too far: he's currently on a distance no more than $$$d$$$ from you.
To find your friend, you can perform the following action no more than $$$400$$$ times: move to any point $$$(x, y)$$$ ($$$-10^6 \le x, y \le 10^6$$$) on the coordinate plane and activate call your friend to check whether he is within a distance of no more than $$$2d$$$ from you.
Find your friend's coordinates with an absolute error of no more than $$$10^{-3}$$$ for each coordinate.
This is an interactive problem.
Interaction with the interactor occurs through queries from your program and responses from the interactor. Each query should be formatted as "? $$$x$$$ $$$y$$$", which means moving to the point with real coordinates $$$x$$$ and $$$y$$$ ($$$-10^6 \le x, y \le 10^6$$$) and calling your friend. In response to the query, you will receive one of two strings:
- "YES", if your friend is within a distance of no more than $$$2d$$$ from the point with coordinates $$$(x, y)$$$;
- "NO" otherwise.
To output the answer to the problem, print "! $$$x_0$$$ $$$y_0$$$", where $$$x_0$$$ and $$$y_0$$$ are the presumed coordinates of your friend's location. This output does not count towards the number of queries.
If at any point your program exceeds the limit of $$$400$$$ queries or you output a query at a point outside the allowed area, the interactor will terminate with a verdict of WA (Wrong Answer).
Remember to output a newline character ('{\}n') after each query and flush the output buffer so that the interactor receives your query. This can be done using std::cout.flush() in C++, System.out.flush() in Java, and sys.stdout.flush() in Python, as well as similar commands in other languages. If your program does not flush the output buffer, it will receive a verdict of TL (Time Limit Exceeded) or IL (Idleness Limit Exceeded).
? 1 0 ? 3 0 ? -1 1 ? 1 1 ? 0 2 ? 2 1 ? 2 1.000001 ? 0 -1.000001 ! 1 0
YES YES NO YES NO YES NO NO
In the first example from the statement, one possible value of $$$d$$$ is $$$1$$$. Then, if we are within a distance of no more than $$$2$$$ from $$$(1, 0)$$$, we get the response YES, otherwise NO.
You play a number game that your suspicious opponent recently learned about. The problem is: if you lose, you may also lose your soul, so it's quite important to win!
The rules of the game are quite simple: there are two positive integers $$$A$$$ and $$$B$$$ and a number $$$k$$$. Players take turns, starting with you. On their turn, a player can perform exactly one of two actions:
- Subtract an integer from $$$1$$$ to $$$k$$$ from the number $$$A$$$;
- Add an integer from $$$1$$$ to $$$k$$$ to the number $$$B$$$.
At the same time, during the game, the numbers $$$A$$$ and $$$B$$$ must remain positive; if a player makes a move that causes one of the numbers to become non-positive, they lose. The player who makes a move such that the sum of the numbers $$$A$$$ and $$$B$$$ becomes a prime number wins the game.
Can you win regardless of your opponent's actions?
Each test contains several sets of input data. The first line of input contains a single integer $$$t$$$ — the number of sets of input data ($$$1 \leq t \leq 10$$$).
The following $$$t$$$ lines describe the sets of input data: each consists of one line containing three integers $$$A$$$, $$$B$$$, $$$k$$$ — the numbers $$$A$$$ and $$$B$$$ at the start of the game and the number $$$k$$$ ($$$1 \leq A, B, k \leq 10^9$$$).
It is guaranteed that $$$A + B$$$ is initially not a prime number.
For each set of input data, output on a separate line "Yes" if you can win with the given initial data, and "No" otherwise.
41 7 23 5 23 6 1253309356 182963670 154154154
No Yes No Yes
Поверхность мира Хайрул усеяна холмами и ущельями, полными опасностей.
Зельда ориентируется по карте Хайрула, на которой отмечено $$$n$$$ локаций. Каждая локация имеет свою высоту над уровнем моря $$$a_i$$$.
Холм — это подпоследовательность локаций (не обязательно идущих подряд, но имеющих возрастающие номера), высоты которых сначала строго возрастают, а затем строго убывают. Иными словами, последовательность $$$i_1, \ldots, i_k$$$ называется холмом, если $$$i_1 \lt i_2 \lt \ldots \lt i_k$$$ и есть некоторое $$$j$$$ от $$$1$$$ до $$$k$$$, что $$$a_{i_1} \lt a_{i_2} \lt \ldots \lt a_{i_j}$$$ и $$$a_{i_j} \gt a_{i_{j+1}} \gt \ldots \gt a_{i_k}$$$. Обратите внимание, что холм может состоять даже из одной локации.
Чтобы спасти Линка и все королевство от неизвестного врага, порождающего порталы в Застывший Мир, необходимо подсчитать количество всех возможных холмов в Хайруле. Казалось бы, это не сильно связанные вещи, но Зельда знает, что делает.
Поскольку холмов может быть очень много, Зельде достаточно найти остаток от деления количества холмов на $$$10^9 + 7$$$. Помогите принцессе справиться с этой задачей.
В первой строке ввода дано целое положительное число $$$n$$$ — число локаций в мире Хайрул ($$$1 \le n \le 10^5$$$).
Во второй строке перечислены $$$n$$$ чисел $$$a_i$$$ — высоты локаций ($$$0 \le a_i \le 10^9$$$).
Выведите одно целое число — остаток от деления общего числа холмов на $$$10^9 + 7$$$.
53 2 5 1 4
20
32 1 3
6
A nameless country consists of $$$n$$$ cities connected by $$$m$$$ bidirectional roads, such that it is possible to reach any city from any other.
There are three factions controlling this country: $$$i$$$-th faction occupies some connected set of cities $$$\{a_{i,j}\}$$$. That is, if we leave only the cities controlled by a specific faction, along with the roads between them, there will be a path between any two of them. It is also known that no city is controlled by more than one faction, meaning $$$a_{i,p} \neq a_{j,q}$$$ for $$$i \neq j$$$.
To celebrate the Equinox you need to mark some cities as main tourist attractions for the celebration. For all the factions so be satisfied, these cities along with factions' cities should form a connected set. Formally, it is necessary to choose a set of cities $$$B$$$ such that any two cities from the set $$$S = B \cup \{a_{i,j}\}$$$ are connected by a path that passes only through cities from $$$S$$$.
Of course, the most obvious way is to mark all the cities in the country, but the government will not be satisfied with such a solution. Find a suitable set $$$B$$$ of minimal size.
The first line contains two integers $$$n$$$ and $$$m$$$ — the number of cities and roads in the country ($$$1 \le n, m \le 2 \cdot 10^5$$$).
The next 6 lines describe the factions: two lines for each. The first line of the description of the $$$i$$$-th faction contains integer $$$k_i$$$ — the number of cities that it controls ($$$1 \le k_i \le n - 2$$$). The second line lists $$$k_i$$$ distinct integers $$$a_{i, j}$$$ — the cities controlled by the $$$i$$$-th faction ($$$1 \le a_{i,j} \le n$$$).
It is guaranteed that each number from $$$1$$$ to $$$n$$$ appears among $$$a_{i,j}$$$ no more than once.
In the next $$$m$$$ lines, the $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ — the cities connected by the $$$i$$$-th road ($$$1 \le u_i, v_i \le n$$$).
It is guaranteed that it is possible to reach any city from any other using the given roads.
In the first line, output an integer $$$b$$$ — the minimum number of cities that you need to mark with for celebration. If the factions are already connected and no cities need to be marked, output $$$0$$$.
In the second line, output $$$b$$$ distinct integers from $$$1$$$ to $$$n$$$ — the numbers of these cities. No city controlled by a faction should be marked.
4 31112134 14 24 3
1 4
10 1231 2 324 5161 22 31 34 51 77 88 99 69 107 1010 54 9
3 9 7 10
An illustration for the second example from the statement is provided in the figure below. Suitable answers include cities $$$7$$$, $$$8$$$, $$$9$$$ or $$$7$$$, $$$9$$$, $$$10$$$.
Making the smoothie is a huge quest, during which you select $$$n$$$ ingredients, represented by numbers from $$$0$$$ to $$$10^9$$$, and arrange them in a sequence $$$a_i$$$. Repeating ingredients is allowed, meaning there could be $$$i$$$ and $$$j$$$ such that $$$a_i = a_j$$$.
Then you need to find the secret ingredient, the number of which is calculated as follows:
- For each $$$i$$$ from $$$1$$$ to $$$n$$$, for the sequence $$$a_1, \ldots, a_{i-1}, a_i$$$, determine $$$b_i$$$ — the smallest number that is not present in this sequence (denoted as $$$\mathrm{mex}(a_1, \ldots, a_i)$$$). For example, $$$\mathrm{mex}(1, 7, 2, 2, 0, 5, 4) = 3$$$ and $$$\mathrm{mex}(1, 4, 5, 2, 3) = 0$$$.
- From the resulting sequence $$$b_1, \ldots, b_n$$$, compute the mex again.
- The final value $$$\mathrm{mex}(b_1, \ldots, b_n)$$$ is taken as the number of the secret ingredient.
Obviously the order of these ingredients can change the number of the secret ingredient. It is known that the higher this number is, the more delicious the smoothie made with it will be.
Arrange the selected ingredients so that the corresponding number of the secret ingredient for the resulting sequence is as large as possible.
The first line of input contains a single integer $$$n$$$ — the number of ingredients you have $$$(1 \leq n \leq 2 \cdot 10^5)$$$.
The second line lists $$$n$$$ integers from $$$0$$$ to $$$10^9$$$ — the numbers of these ingredients.
Output a single integer — the maximum possible number of the secret ingredient.
51 1 0 2 5
4
30 0 0
0
In the first example, one way to arrange the ingredients looks like $$$a = [5, 0, 1, 2, 1]$$$. In this case, we get $$$b = [0, 1, 2, 3, 3]$$$, the mex of which is $$$4$$$.
Когда Зельду бросили в тюрьму самозванцы, притворяющиеся королем и министром Хайрула, ей было долгое время нечем заняться. Поэтому она выписала последовательность из n натуральных чисел, после чего стала выполнять с ней следующие действия:
- Каждое нечетное действие Зельда находит минимальное число в последовательности m1, а также второе по величине значение m2 > m1, после чего заменяет один из элементов последовательности, равный m1, на m2.
- Аналогично, каждое четное действие она находит максимальное число M1 и заменяет одно из его вхождений в последовательность на второй максимум M2 < M1.
Как только в последовательности останется не более двух различных чисел, Зельде надоест развлекаться с ней, и она наконец-то начнет предпринимать попытки сбежать из тюрьмы.
Чтобы ускорить этот процесс, определите, на каком ходу последовательность перестанет быть интересна Зельде, и какие значения в ней после этого останутся.
В первой строке ввода дано целое число n — количество чисел в последовательности (1 ≤ n ≤ 105).
Во второй строке перечислены n целых чисел ai — сами элементы последовательности (1 ≤ ai ≤ 105).
В первой строке выведите номер хода, после которого Зельде перестанет быть интересна последовательность. Если последовательность с самого начала не является интересной, выведите 0.
Во второй строке выведите через пробел минимальное и максимальное числа в получившейся последовательности.
3
4 5 6
1
5 6
4
1 2 1 3
2
1 2
6
4 2 2 5 1 3
6
2 3
Зельда нашла способ соптимизировать создание эхо объектов и создала конвейер по их производству.
Конвейер работает почти что по принципу обычной очереди, но также обладает и некоторыми дополнительными функциями: например, если где-то в очереди скопилось много эхо, которые Зельде уже не понадобятся, есть способ их быстро из очереди изъять.
Более подробно, конвейер в каждый момент времени может быть разделен на несколько сегментов, содержащих отрезки подряд идущих элементов очереди. Для работы с конвейером доступны следующие операции:
- добавить элемент $$$x$$$ в конец последнего сегмента очереди;
- получить первый элемент первого сегмента очереди и удалить первый элемент каждого сегмента очереди; если какой-то сегмент после этого становится пустым, он удаляется, а его левый и правый соседи становятся соседними друг с другом;
- разделить $$$i$$$-й по порядку сегмент очереди на первые $$$j$$$ элементов и все оставшиеся; при такой операции $$$i$$$-й сегмент разбивается на два, а относительный порядок сегментов не меняется;
- соединить все сегменты обратно в один сегмент, содержащий все элементы очереди.
Иными словами, порядок сохранившихся элементов в очереди не меняется, а при выполнении операции pop (2) помимо изъятия самого первого элемента очереди, также удаляются первые элементы каждого сегмента.
Для тестирования конвейера Зельда просит вас реализовать структуру данных, поддерживающую все эти операции.
В первой строке ввода даны целые числа $$$n$$$ и $$$q$$$ — изначальное количество элементов в очереди и число запросов ($$$1 \leq n, q \leq 10^5$$$).
Во второй строке ввода перечислены $$$n$$$ целых чисел $$$a_i$$$ — элементы очереди в ее начальном состоянии ($$$1 \leq a_i \leq 10^9$$$).
Далее следует $$$q$$$ запросов, по одному в каждой строке. Формат запросов в соответствии с их описанием в условии следующий: «push $$$x$$$», «pop», «cut $$$i$$$ $$$j$$$» и «restore» ($$$1 \leq x \leq 10^9$$$; $$$1 \leq i \leq S$$$, где $$$S$$$ — количество непустых сегментов в данный момент; $$$1 \leq j \lt C_S$$$, где $$$C_S$$$ — количество элементов в $$$S$$$-м сегменте).
Гарантируется, что все запросы корректны, в частности pop не вызывается при пустом первом сегменте, а cut не порождает пустые сегменты.
На каждый запрос pop выведите на отдельной строке вынимаемый первый элемент очереди.
Гарантируется, что хотя бы один такой запрос будет.
7 8 1 9 239 144 25 16 777 pop pop cut 1 2 pop restore pop pop pop
1 9 239 144 16 777
В первом примере из условия очередь претерпевает следующие изменения:
- $$$[1, 9, 239, 144, 25, 16, 777]$$$;
- $$$[9, 239, 144, 25, 16, 777]$$$;
- $$$[239, 144, 25, 16, 777]$$$;
- $$$[239, 144], [25, 16, 777]$$$;
- $$$[144], [16, 777]$$$;
- $$$[144, 16, 777]$$$;
- $$$[16, 777]$$$;
- $$$[777]$$$;
- $$$[]$$$;
И вот Зельда зашла в новую локацию, и перед ней внезапно появилось $$$n$$$ противников: засада Нулла, не иначе. Для удобства в бою Зельда дала каждому противнику свой номер, кроме этого она быстро выяснила вид каждого противника. Вид противника с номером $$$i$$$ равен $$$k_i$$$, при этом у разных противников может быть один и тот же вид.
Поскольку на Зельду напали внезапно, она не смогла основательно подготовиться к сражению. Однако, благодаря наблюдениям за сражениями Линка, Зельда смогла вспомнить, что некоторые противники образуют между собой связи, делающие их уязвимыми к атакам. Значит, при правильной стратегии можно победить всех одним ударом!
К несчастью, Зельда не очень внимательно следила за сражениями Линка, поэтому смогла заметить лишь $$$n - 1$$$ связь и тот факт, что любые два противника связаны напрямую или косвенно (по цепочке).
Из-за частых конфликтов с отцом принцесса не очень сильна в комбинированных атаках, которые поражают многих врагов за раз. А именно, она может выбрать два вида противников $$$k_i$$$ и $$$k_j$$$, после чего выстрелить в какого-либо врага. Как только выстрел долетает до врага,
- если этот враг не одного из двух выбранных видов, то с ним ничего не происходит;
- иначе, этот враг оказывается повержен, а атака той же силы применяется к связанным с ним врагам(Зельда может выбрать, на кого перейдёт атака);
- для каждого врага, который был атакован по цепочке связей, рекурсивно применяется тот же алгоритм.
Иными словами, за одну атаку Зельда может поразить множество связанных напрямую или косвенно врагов, каждый из которых принадлежит одному из выбранных ей до атаки видов.
Зельда хочет победить за наименьшее количество атак, так как она хочет поскорее прийти на помощь Линку. Она неплохо стреляет, но не уверена, какие виды противников выбирать для каждой атаки и кого ей нужно атаковать. Помогите Зельде с планом битвы, чтобы у неё точно получилось спасти Линка и весь Хайрул.
В первой строке ввода дано одно число $$$n$$$ — количество противников Зельды ($$$1 \leq n \leq 2 \cdot 10^5$$$).
Во второй строке перечислены $$$n$$$ целых чисел $$$k_1, \ldots, k_n$$$ — виды противников ($$$1 \leq k_i \leq n$$$).
В $$$i$$$-й из следующих $$$n - 1$$$ строках даны два целых числа $$$v_i$$$ и $$$u_i$$$, означающие, что атака по противнику $$$v_i$$$ перейдёт на противника $$$u_i$$$ и наоборот ($$$1 \le v_i, u_i \le n$$$; $$$v_i \neq u_i$$$). Гарантируется, что такие связи косвенно связывают любую пару противников.
В первой строке необходимо вывести минимальное количество атак $$$a$$$.
В следующих $$$a$$$ строках необходимо вывести список противников, пораженных каждой атакой. Строка, описывающая $$$i$$$-ю атаку, должна начинаться с числа $$$n_i$$$ — количества поверженных противников, за которым через пробел должны быть перечислены $$$n_i$$$ номеров поверженных противников от $$$1$$$ до $$$n$$$.
Каждый враг должен быть выведен ровно один раз.
66 6 2 1 6 41 64 31 23 52 3
3 4 1 2 3 5 1 4 1 6
54 5 4 4 54 52 55 13 5
1 5 1 2 5 3 4
You have to transport a large tree. The tree is rooted and consists of $$$n$$$ vertices with the root at vertex $$$1$$$, and each vertex has its own weight $$$a_i$$$. The weight of a tree is a total weight of its vertices.
Sadly the tree exceeds the capacity of your backpack by $$$w$$$ units of weight.
So in one action, you can choose a certain vertex $$$v$$$ and cut it off along with its subtree (all vertices $$$u$$$ such that a path between $$$u$$$ and root contains $$$v$$$). Your goal is to cut vertices with a total weight of exactly $$$w$$$.
Determine if it's possible.
The first line of input contains two integers $$$n$$$ and $$$w$$$ — the number of vertices in the tree and the required weight of the vertices to be removed ($$$1 \le n, w \le 1000$$$).
The second line of input contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ — the weights of the vertices ($$$1 \le a_i \le 100$$$).
In each of the next $$$n - 1$$$ lines, there are two integers $$$u_i$$$ and $$$v_i$$$ — the numbers of the vertices connected by the $$$i$$$-th edge. It is guaranteed that the given graph is a tree ($$$1 \le u, v \le n$$$; $$$u \neq v$$$).
If it is impossible to cut off vertices with a total weight of $$$w$$$ using the described actions, output $$$-1$$$.
Otherwise, first output an integer $$$k$$$ from $$$0$$$ to $$$n$$$ — the number of cuts. Then output $$$k$$$ distinct integers from $$$1$$$ to $$$n$$$ — the numbers of the vertices that need to be cut off. No two printed vertices should be a child and an ancestor.
If there are multiple suitable sequences of actions, output any.
5 73 4 3 2 21 22 32 44 5
2 4 3
5 83 4 3 2 21 22 32 44 5
-1
5 143 4 3 2 21 22 32 44 5
1 1
In the first example, you can cut off vertices $$$3$$$ and $$$4$$$, and along with vertex $$$4$$$, you will also cut off vertex $$$5$$$, since vertex $$$5$$$ is in a subtree of vertex $$$4$$$. The total weight of the removed vertices $$$3$$$, $$$4$$$, $$$5$$$ equals $$$3 + 2 + 2 = 7$$$.
У принцессы Зельды была колода из $$$n$$$ карт. На каждой карте было написано целое число от $$$1$$$ до $$$n$$$, причём изначально не было двух карт с одинаковыми числами на них. Затем она использовала силу волшебного Жезла Трифа и создала копию каждой карты.
К сожалению, карты упали на землю рубашками вверх, и теперь нужно снова собрать все карты по парам, иначе ими не получится пользоваться.
Просто перевернуть все карты было бы слишком скучно, поэтому Зельда решила выбирать по две карты и смотреть, совпали ли их значения. Если совпали, то она их откладывает в сторону, и выбирает следующую пару карт. Иначе она переворачивает эти карты обратно и выбирает пару карт заново.
Единственное, что Зельде известно изначально — если пронумеровать все лежащие на земле карточки от $$$1$$$ до $$$2n$$$, то значение на карточке под номером $$$a$$$ строго меньше, чем на карточке под номером $$$b$$$.
Несмотря на желание сделать процесс сортировки карт интересным, принцесса очень спешит, поэтому хочет закончить за не более чем $$$2n - 1$$$ ход. Помогите ей в этом!
В первой строке даны три целых числа $$$n$$$, $$$a$$$ и $$$b$$$ — количество карточек, которые изначально были у Зельды, а также номера двух карточек, про значения которых известно, что первое меньше второго ($$$2 \le n \le 50\,000$$$; $$$1 \le a, b \le 2n$$$; $$$a \ne b$$$).
После считывания ввода вашей программой запускается процесс взаимодействия с интерактором.
В процессе взаимодействия с интерактором ваша программа должна сообщать интерактору запросы в формате «? $$$x$$$ $$$y$$$», где $$$x$$$ и $$$y$$$ — два различных целых числа от $$$1$$$ до $$$2n$$$, обозначающие номера карточек, которые Зельда должна перевернуть на очередном ходу.
В ответ интерактор в отдельной строке напечатает через пробел два целых числа от $$$1$$$ до $$$n$$$ — значения, написанные на этих карточках. Если значения совпали, эти карточки убираются и больше не должны упоминаться в запросах.
Если какой-то из сделанных вашей программой запросов будет некорректен, интерактор выведет «-1 -1» и завершится с вердиктом WA (Wrong Answer). Также если ваша программа превысит лимит в $$$2n - 1$$$ запрос, интерактор завершится тем же образом.
Если же ваша программа сможет на $$$2n - 1$$$ запрос или меньше перевернуть все карточки по парам с одинаковыми значениями, интерактор завершится с вердиктом OK. Во избежание получения вердиктов TL (Time Limit Exceeded) или IL (Idleness Limit Exceeded) ваша программа также должна завершаться с кодом возврата $$$0$$$ после успешного ответа интерактора на последний запрос.
Также обратите внимание, что вывод каждого запроса должен завершаться переводом строки (символ '{\}n') и сбросом буфера вывода (sys.stdout.flush() в Python, cout.flush() в C++, System.out.flush() в Java и аналогичными методами в других языках).
2 1 4 1 1 2 2
1 3 2 4
3 5 3 3 2 3 3 1 2 2 2 1 1
3 5 3 4 1 5 2 5 1 6