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

Есть загаданное дерево, состоящее из $$$n$$$ вершин, которое имеет только один центроид. Сначала вам известно только $$$n$$$, и ваша задача  — найти центроид дерева.

Вы можете спросить расстояние между любыми двумя вершинами не более $$$2\cdot10^5$$$ раз.

Обратите внимание, что интерактор является неадаптивным. То есть, дерево фиксировано в каждом тесте заранее и не зависит от ваших запросов.

Вершина называется центроидом, если ее удаление разбивает дерево на поддеревья, в каждом из которых не более $$$\lfloor\frac{n}{2}\rfloor$$$ вершин.

Начните взаимодействие с чтения $$$n$$$.

Чтобы задать запрос о расстоянии между двумя вершинами $$$u, v$$$ ($$$1 \le u, v \le n$$$), выведите «? u v».

Если вы определили, что центроидом дерева является $$$x$$$, используйте «! x» для вывода ответа.

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

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

В этой задаче взломы отключены.

Гарантируется, что в этой задаче есть не более $$$500$$$ тестов.