Дано дерево $T = (V, E)$ с $N$ вершинами. Для последовательности $\{a_1, \dots, a_k\}$ вершин дерева $T$ длины $k$ определим её оценку следующим образом: - Пусть $d(u, v)$ — количество рёбер на пути между вершинами $u$ и $v$ в $T$. Тогда оценка равна $\prod_{i=1}^{k} d(a_i, a_{(i \bmod k)+1})$.

Дано подмножество $S \subseteq V$. Для каждого $1 \le k \le N$ найдите следующее значение $q_k$: - Сумма оценок по всем последовательностям вершин $\{a_1, \dots, a_k\}$ длины $k$, элементы которых принадлежат $S$, взятая по модулю $2^{61} - 1$.

Программа заранее хранит информацию о дереве $T$ и продолжает использовать $T$ как дерево, данное программе. Вы пытаетесь восстановить информацию о листьях, используя вышеупомянутую программу. Пусть $N$ — количество вершин дерева, вы можете задать следующий вопрос не более $N$ раз: - Выберите подмножество $S \subseteq V$ и запросите вывод программы.

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

Протокол взаимодействия

Сначала $N$ подается со стандартного ввода ($2 \le N \le 50$). Для каждого вопроса выведите в стандартный вывод в следующем формате: ? $s_1s_2 \dots s_N$

Здесь $s_1s_2 \dots s_N$ — строка длины $N$, представляющая подмножество $S$, где $s_i = 1$, если $i \in S$, и $s_i = 0$, если $i \notin S$. В ответ со стандартного ввода подается следующее: $q_1 \ q_2 \ \dots \ q_N$

Как только вы определили все листья, выведите ответ в следующем формате: ! $t_1t_2 \dots t_N$

Здесь $t_1t_2 \dots t_N$ — строка длины $N$, где $t_i = 1$, если $i$ — лист, и $t_i = 0$, если это не лист. После этого вывода немедленно завершите работу программы. При каждом выводе добавляйте символ переноса строки и очищайте буфер стандартного вывода.

Примеры

Входные данные 1

5
0 8 0 32 0
0 44 108 968 3960
0 0 0 0 0
0 76 348 3336 22200

Выходные данные 1

? 00101
? 11001
? 10000
? 11111
! 11001

Примечание

Для первого примера множество рёбер дерева, тайно хранящееся у жюри, — $(1, 3), (2, 3), (3, 4), (4, 5)$. В первом вопросе $S = \{3, 5\}$. Заметим, что $d(3, 3) = 0, d(3, 5) = d(5, 3) = 2, d(5, 5) = 0$. Для примера, существуют следующие 4 последовательности вершин $a$ длины 2, элементы которых принадлежат $S$:

• Если $a = (3, 3)$, то оценка этой последовательности равна $d(3, 3) \times d(3, 3) = 0 \times 0 = 0$
• Если $a = (3, 5)$, то оценка этой последовательности равна $d(3, 5) \times d(5, 3) = 2 \times 2 = 4$
• Если $a = (5, 3)$, то оценка этой последовательности равна $d(5, 3) \times d(3, 5) = 2 \times 2 = 4$
• Если $a = (5, 5)$, то оценка этой последовательности равна $d(5, 5) \times d(5, 5) = 0 \times 0 = 0$

Жюри отвечает 8 для $q_2$, что является остатком от деления $0 + 4 + 4 + 0$ на $2^{61} - 1$. Вычисляя аналогично для других длин последовательностей, мы получаем ответ жюри $0 \ 8 \ 0 \ 32 \ 0$. Листьями этого дерева являются вершины $1, 2, 5$, и вывод ! 11001 корректно завершает идентификацию листьев.