Это интерактивная задача.

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

Как известно, для запуска алгоритма Флойда в графе на $$$n$$$ вершинах должно быть по одному ребру между любыми двумя вершинами. У ученых есть такой граф, однако, они ориентировали каждое ребро, то есть направили его ровно в одну из двух сторон.

Для оптимизации Флойда выбраны $$$m$$$ рёбер и покрашены в розовый цвет, остальные ребра покрашены в зеленый. Вы знаете направление каждого из этих $$$m$$$ ребер, однако, направление зеленых рёбер вам заранее неизвестно. За один запрос вы можете узнать направление одного зеленого ребра, но всего вы можете сделать не более $$$2 \cdot n$$$ запросов.

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

Чтобы узнать направление зеленого ребра между вершинами $$$a$$$ и $$$b$$$, в одной строке через пробел выведите символ «?», а затем два целых числа $$$a$$$ и $$$b$$$.

В ответ на это считайте целое число, которое будет равно $$$1$$$, если ребро направленно от $$$a$$$ к $$$b$$$, и $$$0$$$, если ребро направлено от $$$b$$$ к $$$a$$$.

Вы можете задать не более $$$2 \cdot n$$$ вопросов, в противном случае вы получите вердикт Wrong Answer.

После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

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

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

Взломы

Для взлома задайте тест в следующем формате. В первой строке должны находиться два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 300$$$, $$$0 \le m \le n \cdot (n - 1) / 2$$$) — число вершин и число рёбер розового цвета.

В $$$i$$$-й из следующих $$$m$$$ строк должны находиться два целых чисел $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \ne b_i$$$)), означающих, что есть ребро розового цвета от вершины $$$a_i$$$ к вершине $$$b_i$$$. Все неориентированные пары $$$(a_i, b_i)$$$ должны быть различны.

В $$$i$$$-й из следующих $$$(n \cdot (n - 1) / 2 - m)$$$ строках должны находиться два целых числа $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \ne b_i$$$)), означающих, что есть ребро зеленого цвета от вершины $$$a_i$$$ к вершине $$$b_i$$$. Все неориентированные пары $$$(a_i, b_i)$$$ должны быть различны и не должны совпадать с теми же парами для рёбер розового цвета.