To zadanie jest interaktywne. Po wypisaniu każdej linii należy opróżnić bufor wyjścia (flush). Możesz użyć cout << flush w C++, System.out.flush() w Javie oraz sys.stdout.flush() w Pythonie. Musisz ściśle przestrzegać instrukcji w sekcji Interakcja; w przeciwnym razie możesz otrzymać werdykt taki jak błędna odpowiedź (wrong answer), przekroczenie limitu czasu (time limit exceeded) lub inny.

Ponieważ we wszystkich zadaniach głównymi bohaterami są mityczne krasnoludy, być może warto wreszcie pomyśleć o czymś namacalnym.

Dany jest ukryty ciąg $A$ długości $N$, składający się z liczb całkowitych z przedziału $[0, 2^N - 1]$. Twoim zadaniem jest odtworzenie go przy użyciu ograniczonej liczby zapytań. W każdym zapytaniu podajesz ciąg $B$ długości $N$ o elementach z przedziału $[0, 2^N - 1]$. Odpowiedź jest obliczana w następujący sposób:

• Tworzony jest ciąg $C$, w którym $i$-ty element ciągu $C$ jest bitowym xor-em (bitwise xor) $i$-tych elementów ciągów $A$ oraz $B$. Operację xor oznaczamy symbolem $\oplus$.
• Konstruowany jest zbiór $S$ jako zbiór wszystkich wartości, które można uzyskać poprzez wykonanie operacji xor na pewnym podzbiorze elementów ciągu $C$. W szczególności dla podzbioru pustego xor wynosi $0$.
• Odpowiedzią na zapytanie jest $|S|$.

Na przykład, jeśli $A = (1, 4, 3)$ oraz $B = (0, 4, 7)$, to $C = (1 \oplus 0, 4 \oplus 4, 3 \oplus 7) = (1, 0, 4)$ oraz $S = \{0, 1, 4, 5\}$, więc odpowiedzią jest $4$.

Bitowy xor dwóch liczb $x$ i $y$ ma zapalony bit $i$ wtedy i tylko wtedy, gdy dokładnie jedna z liczb $x$ i $y$ ma zapalony bit $i$. Na przykład $5 \oplus 3 = (101)_2 \oplus (011)_2 = (110)_2 = 6$. W C++ oraz Pythonie xor to operator ^.

Interakcja

Ciąg $A$ jest ustalony na początku i nie zależy od zadawanych zapytań.

Najpierw wczytaj linię zawierającą jedną liczbę całkowitą $1 \le N \le 60$. Następnie możesz zadawać zapytania.

Aby zadać zapytanie, wypisz linię zawierającą znak ?, a po nim $N$ liczb całkowitych z przedziału $[0, 2^N - 1]$. W odpowiedzi wczytaj jedną liczbę całkowitą będącą wynikiem.

Gdy będziesz gotowy, wypisz znak !, a po nim $N$ liczb całkowitych tworzących ukryty ciąg. Następnie Twój program powinien zakończyć działanie bez wypisywania czegokolwiek więcej.

Pamiętaj o opróżnianiu bufora wyjścia (flush) po każdym zapytaniu oraz po wypisaniu odpowiedzi. Oddzielaj spacjami liczby oraz symbole ?, !.

Przykłady

Wejście 1

3
4
8

Wyjście 1

? 1 2 3
? 0 0 0
! 1 3 4

Uwaga

Wyjaśnienie przykładowej interakcji: $N = 3$ Zapytanie ? 1 2 3: $B = (1, 2, 3)$, $C = (1 \oplus 1, 3 \oplus 2, 4 \oplus 3) = (0, 1, 7)$, $S = \{0, 1, 6, 7\}$, odpowiedź to $4$. Zapytanie ? 0 0 0: $B = (0, 0, 0)$, $C = (1 \oplus 0, 3 \oplus 0, 4 \oplus 0) = (1, 3, 4)$, $S = \{0, 1, \dots, 7\}$, odpowiedź to $8$. Wyjście ! 1 3 4: Ukryty ciąg to $A = (1, 3, 4)$.

Testowanie lokalne

W sekcji Files znajdziesz plik B.zip zawierający testy przykładowe oraz oceniaszkę grader.cpp. Aby przetestować swoje rozwiązanie, skompiluj je, a następnie przekaż nazwę testu oraz swój plik wykonywalny do skompilowanego programu ./grader:

./grader [test] [executable]

Na przykład: ./grader 0b.in ./abc

Przykładowa oceniaszka nie musi działać identycznie jak oficjalna. Żadna z nich nie jest jednak adaptacyjna.