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

Вам дано целое число $$$n$$$.

Жюри загадало ориентированный граф с $$$n$$$ вершинами (пронумерованными от $$$1$$$ до $$$n$$$) и с некоторым количеством рёбер. Дополнительно известно, что:

• Граф содержит рёбра только вида $$$i \leftarrow j$$$, где $$$1 \le i < j \le n$$$.
• Для любых трёх вершин $$$1 \le i < j < k \le n$$$ верно хотя бы одно из следующего$$$^\dagger$$$:
  • Вершина $$$i$$$ достижима из вершины $$$j$$$, или
  • Вершина $$$i$$$ достижима из вершины $$$k$$$, или
  • Вершина $$$j$$$ достижима из вершины $$$k$$$.

Вы хотите покрасить каждую вершину графа либо в белый, либо в чёрный цвет так, чтобы для любых двух вершин $$$i$$$ и $$$j$$$ ($$$1 \le i < j \le n$$$) одного цвета вершина $$$i$$$ была достижима из вершины $$$j$$$.

Для этого вы можете делать запросы следующего вида:

• ? i j — достижима ли вершина $$$i$$$ из вершины $$$j$$$ ($$$1 \le i < j \le n$$$)?

Найдите любую подходящую раскраску вершин графа за не более чем $$$2 \cdot n$$$ запросов. Можно доказать, что такая раскраска всегда существует.

Примечание: интерактор не является адаптивным, то есть граф фиксируется до выполнения каких-либо запросов.

$$$^\dagger$$$ Вершина $$$a$$$ достижима из вершины $$$b$$$ если в графе существует путь из вершины $$$b$$$ в вершину $$$a$$$.

Взаимодействие для каждого набора входных данных начинается с чтения целого числа $$$n$$$.

Для формирования запроса выведите «? i j» без кавычек ($$$1 \le i < j \le n$$$). Если вершина $$$i$$$ достижима из вершины $$$j$$$, вы получите в ответ YES. Иначе, вы получите в ответ NO.

Если вместо ответа или допустимого значения $$$n$$$ вы получите целое число $$$-1$$$, то это означает, что ваша программа сделала некорректный запрос, превысила лимит запросов или дала неверный ответ на предыдущем наборе входных данных. При получении вердикта «Неправильный ответ» ваша программа должна немедленно завершиться. В противном случае можно получить произвольный вердикт, поскольку решение будет продолжать считывать данные из закрытого потока.

Когда вы будете готовы дать окончательный ответ, выведите «! $$$c_1 \ c_2 \ \ldots \ c_n$$$» без кавычек — раскраска вершин графа, где $$$c_i = 0$$$, если вершина чёрная, и $$$c_i = 1$$$, если вершина белая. После решения одного набора входных данных программа должна сразу же переходить к следующему. После решения всех наборов входных данных программа должна быть немедленно завершена.

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

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

Взломы

Для взлома используйте следующий формат:

Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$3 \le n \le 100$$$, $$$0 \le m \le \frac{n\cdot(n - 1)}{2}$$$) — количество вершин и рёбер в графе.

Следующие $$$m$$$ строк должны содержать два числа $$$a$$$ и $$$b$$$ ($$$1 \le b < a \le n$$$), означающие, что в графе присутствует ребро $$$a \rightarrow b$$$. Граф должен удовлетворять условиям выше.

Сумма $$$n$$$ по всем наборам входных данных не должна превышать $$$1000$$$.