Рэй потерял свой массив и должен найти его, спросив Омкара. Омкар готов раскрыть, что массив обладает следующими качествами:

1. Массив содержит $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) элементов.
2. Каждый элемент в массиве $$$a_i$$$ является целым числом в диапазоне $$$1 \le a_i \le 10^9.$$$
3. Массив отсортирован в порядке неубывания.

Рэй может отправить Омкару серию запросов. Запрос состоит из двух целых чисел, $$$l$$$ и $$$r$$$, таких, что $$$1 \le l \le r \le n$$$. Омкар ответит двумя целыми числами, $$$x$$$ и $$$f$$$. $$$x$$$  — мода подмассива от индекса $$$l$$$ до индекса $$$r$$$ включительно. Модой массива называют число, которое встречается в нем чаще всего. Если есть несколько чисел, которые встречаются наибольшее количество раз, модой считается наименьшее из них. $$$f$$$  — это количество раз, которое $$$x$$$ встречается в запрашиваемом подмассиве.

Массив имеет $$$k$$$ ($$$1 \le k \le \min(25000,n)$$$) различных элементов. Однако из-за грехов Рэя Омкар не скажет Рэю, чему равно $$$k$$$. Рэю разрешено отправить не более $$$4k$$$ запросов.

Помогите Рэю найти его потерянный массив.

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

Затем вы можете сделать один тип запроса:

• "$$$? \enspace l \enspace r$$$" ($$$1 \le l \le r \le n$$$) где $$$l$$$ и $$$r$$$ это границы подмассива, который вы хотите запросить.

Ответ на каждый запрос будет иметь вид "$$$x \enspace f$$$", где $$$x$$$  — это мода подмассива, а $$$f$$$  — количество раз, которое $$$x$$$ встречается в подмассиве.

• $$$x$$$ удовлетворяет ($$$1 \leq x \leq 10^9$$$).
• $$$f$$$ удовлетворяет ($$$1 \leq f \leq r-l+1$$$).
• Если вы делаете более $$$4k$$$ запросов или нарушаете диапазон номеров в запросе, вы получите вывод "-1."
• Если вы прекратите работу после получения ответа "$$$-1$$$", вы получите вердикт "Неправильный ответ ". В противном случае вы можете получить произвольный вердикт, потому что ваше решение будет продолжать читать из закрытого потока.

Чтобы вывести ответ, выведите:

• "$$$! \enspace a_1 \enspace a_2 \enspace \ldots \enspace a_{n-1} \enspace a_n$$$", который является восклицательным знаком, за которым следует массив с пробелом между каждым элементом.

После этого завершите программу. Этот запрос не учитывается в лимит запросов $$$4k$$$.

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

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

Формат взломов

Для взлома выведите $$$1$$$ целое число в первой строке: $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$). Во второй строке выведите $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_{n-1}, a_n$$$, разделенных пробелами. Среди них должно быть не более $$$25000$$$ различных чисел и $$$a_j \le a_{j+1}$$$ должно выполняться для всех $$$j$$$ от $$$1$$$ до $$$n-1$$$.