KUPC-kun napisał program, który rozwiązuje następujący problem: Dano drzewo $T = (V, E)$ o $N$ wierzchołkach. Dla ciągu $\{a_1, \dots, a_k\}$ wierzchołków drzewa $T$ o długości $k$, zdefiniujmy jego wynik w następujący sposób: - Niech $d(u, v)$ oznacza liczbę krawędzi na ścieżce między wierzchołkami $u$ oraz $v$ w $T$. Wtedy wynik wynosi $\prod_{i=1}^{k} d(a_i, a_{(i \bmod k)+1})$.

Dany jest podzbiór $S$ zbioru $V$. Dla każdego $1 \le k \le N$ należy wyznaczyć następującą wartość $q_k$: - Suma wyników wszystkich ciągów wierzchołków $\{a_1, \dots, a_k\}$ o długości $k$, których elementy należą do $S$, obliczona modulo $2^{61} - 1$.

KUPC-kun potajemnie przechowuje informacje o drzewie $T$ i używa tego samego drzewa $T$ w programie. Twoim zadaniem jest odzyskanie informacji o liściach drzewa za pomocą powyższego programu. Znając liczbę wierzchołków drzewa $N$, możesz zadać co najwyżej $N$ pytań: - Wybierz podzbiór $S \subseteq V$ i poproś o wynik działania programu.

Zakładając, że program KUPC-kuna jest poprawny, zidentyfikuj wszystkie liście w drzewie $T$ na podstawie informacji uzyskanych z pytań. Sędzia nie jest adaptacyjny, a drzewo $T$ jest ustalone przed rozpoczęciem interakcji.

Interakcja

Najpierw z wejścia standardowego wczytywana jest liczba $N$ ($2 \le N \le 50$). Dla każdego pytania wypisz na wyjście standardowe zapytanie w następującym formacie: ? $s_1s_2 \dots s_N$

Tutaj $s_1s_2 \dots s_N$ jest ciągiem o długości $N$ reprezentującym podzbiór $S$, gdzie $s_i = 1$, jeśli $i \in S$, oraz $s_i = 0$, jeśli $i \notin S$. W odpowiedzi z wejścia standardowego otrzymasz: $q_1 \ q_2 \ \dots \ q_N$

Po zidentyfikowaniu wszystkich liści wypisz odpowiedź w następującym formacie: ! $t_1t_2 \dots t_N$

Tutaj $t_1t_2 \dots t_N$ jest ciągiem o długości $N$, gdzie $t_i = 1$, jeśli $i$ jest liściem, oraz $t_i = 0$, jeśli nie jest liściem. Po wypisaniu odpowiedzi natychmiast zakończ działanie programu. Po każdej operacji wyjścia należy dodać znak nowej linii i opróżnić bufor wyjścia.

Przykład

Wejście 1

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

Wyjście 1

? 00101
? 11001
? 10000
? 11111
! 11001

Uwagi

Dla pierwszego przykładu zbiór krawędzi drzewa potajemnie przechowywany przez sędziego to $(1, 3), (2, 3), (3, 4), (4, 5)$. W pierwszym pytaniu $S = \{3, 5\}$. Zauważ, że $d(3, 3) = 0, d(3, 5) = d(5, 3) = 2, d(5, 5) = 0$. Na przykład, istnieje 4 ciągów wierzchołków $a$ o długości 2, których elementy należą do $S$:

• Jeśli $a = (3, 3)$, to wynik tego ciągu wynosi $d(3, 3) \times d(3, 3) = 0 \times 0 = 0$
• Jeśli $a = (3, 5)$, to wynik tego ciągu wynosi $d(3, 5) \times d(5, 3) = 2 \times 2 = 4$
• Jeśli $a = (5, 3)$, to wynik tego ciągu wynosi $d(5, 3) \times d(3, 5) = 2 \times 2 = 4$
• Jeśli $a = (5, 5)$, to wynik tego ciągu wynosi $d(5, 5) \times d(5, 5) = 0 \times 0 = 0$

Sędzia odpowiada $8$ dla $q_2$, co jest resztą z dzielenia $0 + 4 + 4 + 0$ przez $2^{61} - 1$. Obliczając analogicznie dla innych długości ciągów, otrzymujemy odpowiedź sędziego $0 \ 8 \ 0 \ 32 \ 0$. Liśćmi tego drzewa są wierzchołki $1, 2, 5$, więc wypisanie ! 11001 poprawnie kończy identyfikację liści.