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

Диксит живет в городе, в котором $$$n$$$ домов. Между каждой парой домов есть ровно одна направленная дорога. То есть для любой пары домов A и B есть либо дорога от дома A к дому B, либо дорога от B к A (но только одна из них). К $$$i$$$-му дому ведут $$$k_i$$$ дорог.

Два дома A и B являются взаимно достижимыми, если дом A достижим из дома B (существует путь от дома A к дому B по дорогам), и дом B достижим из дома A.

Диксит хочет купить в этом городе два дома, один для того, чтобы жить в нем, другой — для учебы. Естественно, он бы хотел, чтобы от каждого из этих домов можно было добраться до другого дома, то есть ему нужно найти пару взаимно достижимых домов. Если таких пар несколько, Диксит хочет максимизировать величину $$$|k_A - k_B|$$$, где $$$k_i$$$ — количество дорог, ведущих к дому $$$i$$$. Если существует более одной оптимальной пары, подойдет любая из них.

Так как Диксит занят подготовкой CodeCraft, он просит вас помочь ему найти два таких дома, или сообщить, что таких домов нет.

Во входных данных задачи вам не задаются направления дорог. Вы знаете только количество дорог, идущих к каждому дому ($$$k_i$$$).

Вы можете задавать запросы следующих типов: вы выводите пару домов A и B, и жюри ответит, есть ли путь от дома A к дому B. В этой задаче нет никакого явного ограничения на количество запросов, которые вы можете задать. Но нельзя задавать запросы после того, как жюри ответит «Yes» на один из ваших запросов. Кроме того, нельзя задавать один и тот же запрос дважды.

Как только вы зададите все необходимые запросы (или жюри ответит «Yes» на один из них), ваша программа должна вывести ответ и завершиться.

Прочтите раздел «Протокол взаимодействия» для того, чтобы получить более подробную информацию о взаимодействии.

Чтобы задать запрос, выведите «? A B» $$$(1 \leq A,B \leq N, A\neq B)$$$. Программа жюри ответит «Yes», если есть путь от дома A к дому B, или «No», если пути нет.

Чтобы дать ответ на задачу, выведите «! A B», где A и B — номера двух различных домов, достижимых друг из друга, с максимально возможной величиной $$$|k_A - k_B|$$$. Если такой пары домов не существует, выведите «! 0 0».

После вывода ответа ваша программа должна завершиться, иначе вы получите вердикт «Неправильный ответ».

Вы не можете задавать один и тот же запрос дважды. Нет никакого ограничения на количество запросов, но вы не можете задавать запросы после получения ответа «Yes». После этого ваша программа сразу должна вывести ответ на задачу («! A B» или «! 0 0») и завершиться.

Если вы зададите запрос в неправильном формате или зададите один и тот же запрос дважды, вы получите вердикт «Неправильный ответ».

После вывода запроса не забудьте вывести символ конца строки и сбросить буфер вывода (иначе вы можете получить вердикт «Решение зависло»). В различных языках программирования сброс буфера вывода реализован следующим образом:

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