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

В этой интерактивной задаче вам дан ацикличный, связный и неориентированный граф, состоящий из $$$n$$$ вершин. Назовем путем между двумя вершинами $$$v$$$ и $$$u$$$ последовательность различных вершин $$$p_1, p_2,\dots p_k$$$ такую, что $$$p_1 = v$$$, $$$p_k = u$$$ и для всех $$$i$$$ ($$$1 \le i \lt k$$$) существует ребро между вершинами $$$p_i$$$ и $$$p_{i+1}$$$.

Есть скрытые вершины $$$x$$$ и $$$y$$$ (они могут совпадать). Вы можете делать следующие запросы:

• Выберите две вершины $$$a$$$, $$$b$$$ ($$$1\le a, b\le n$$$). Жюри ответит $$$1$$$, если путь между вершинами $$$x$$$, $$$y$$$ и путь между вершинами $$$a$$$, $$$b$$$ содержит хотя бы одну общую вершину, и ответит $$$0$$$ в противном случае.

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

Для нахождения одной любой вершины на пути вы можете использовать не более $$$\lfloor\frac{n}{2}\rfloor + 1$$$ запросов. Для этого используйте запросы вида «? $$$a$$$ $$$b$$$».

После каждого запроса считайте одно число, равное $$$0$$$ или $$$1$$$ — ответ на запрос.

Когда вы найдете одну из нужных вершин, выведите одну строку следующего формата: «! $$$v$$$» ($$$1\le v\le n$$$), где $$$v$$$ это вершина, которую вы нашли.

Если ваша программа сделает более $$$\lfloor\frac{n}{2}\rfloor + 1$$$ запросов для одного набора входных данных, то ответом на запрос будет $$$-1$$$, после получения такого ответа ваша программа должна немедленно завершиться, чтобы получить вердикт Неправильный ответ. Иначе она может получить любой другой вердикт.

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

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