Вы достигли финального уровня популярной игры в жанре roguelike «Сочетания клавиш Исаака». Вместо босса вы встречаете торговца, у которого есть скрытый массив целых чисел $$$a_1, a_2, \ldots, a_n$$$, где $$$0 \leq a_i \lt 2^{30}$$$ для каждого $$$i$$$ в $$$[1, n]$$$.

Гарантируется, что массив сгенерирован случайным образом, то есть каждый $$$a_i$$$ ($$$1 \leq i \leq n$$$) является целым числом, независимо и равномерно выбранным из $$$[0, 2^{30})$$$, во всех тестах, кроме примера.

Обозначим $$$f(u, v) = a_u \oplus a_{u+1} \oplus \ldots \oplus a_v$$$, где $$$\oplus$$$ — это побитовый $$$\texttt{XOR}$$$.

Вы можете задавать запросы следующего вида: $$$\texttt{? u v}$$$, с $$$1 \leq u \leq v \leq n$$$.

Ответ на запрос:

• $$$-1$$$, если $$$f(u, v) = 0$$$;
• $$$\lfloor \log_2(f(u, v)) \rfloor$$$ в противном случае.

Каждый запрос стоит $$$\frac{1}{v-u+1}$$$ робокоина. В каждом тесте вам дается в общей сложности $$$300$$$ робокоинов, чтобы пройти не более $$$30$$$ наборов входных данных (то есть вы должны потратить в среднем $$$10$$$ робокоинов на один набор входных данных). Если ваш баланс когда-либо станет отрицательным, вы проиграете. Обратите внимание, что ваш баланс робокоинов не обязательно должен быть целым числом в любой момент времени.

Найдите ответы на все возможные $$$\frac{n(n+1)}{2}$$$ запросов, не проиграв.

Для каждого набора входных данных сначала прочитайте одно целое число $$$n$$$. Если прочитанное вами число равно $$$-2$$$, это означает, что ответ на предыдущий набор входных данных был неверным, и вы должны немедленно выйти.

Чтобы задать запрос, выведите строку в формате $$$\texttt{? u v}$$$, где $$$1 \leq u \leq v \leq n$$$.

Если вы сделали недопустимый запрос (т.е. формат неверен или вы достигли отрицательной суммы робокоинов), в ответ на запрос вы получите $$$-2$$$. В этом случае вы должны немедленно выйти. В противном случае вы получите ответ на запрос.

Когда вы определите ответы на все $$$\frac{n(n+1)}{2}$$$ запросов, выведите их в следующем формате.

Выведите $$$n+1$$$ строк. Первая строка должна содержать один символ $$$\texttt{!}$$$. $$$i$$$-я из следующих $$$n$$$ строк должна содержать $$$n-i+1$$$ целых чисел: ответы на запросы $$$\texttt{? i i}, \, \texttt{? i i+1}, \,\ldots, \, \texttt{? i n}$$$ соответственно.

После вывода запроса не забудьте вывести конец строки и сбросить вывод. В противном случае вы получите $$$\texttt{Idleness limit exceeded}$$$. Для этого используйте:

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