Мережа Дюлока

Обмеження: 2 сек., 512 МіБ

Це інтерактивна задача (де ваша програма взаємодіє з програмою журі через ввід та вивід).

У королівстві Дюлок, Лорд Фаркуад розвиває мережу веж для моніторингу кожного куточка своєї землі. У нього є карта веж та доріг, що їх з’єднують, утворюючи неорієнтований простий граф $G=(V,E)$, де кожна вежа — це вершина, а кожна дорога — це ребро між двома вежами. Однак Фаркуад хвилюється, що деякі частини Дюлока можуть бути ізольовані, що зробить неможливим доступ до кожної вежі з будь-якої іншої.

Щоб забезпечити повну зв’язність, він доручає вам перевірити, чи є його мережа з’єднаною. Проте є одна умова: вам дозволено обмежений доступ до інформації про граф.

Ви можете робити запити про мережу, щоб перевірити її зв’язність. Запит дозволяє вибрати підмножину веж $S$ і отримати кількість веж, що не належать $S$ і напряму з’єднані з хоча б однією вежею з $S$. Тобто, $query(S) = |N(S) \setminus S|$, де $S \subseteq V$ і $N(S) = \{x \vert \exists y \in S \text{ such that } (x, y) \in E\}$.

Ваше завдання — ефективно використовувати ці запити, щоб перевірити, чи мережа є зв’язною.

Чи можете ви допомогти Лорду Фаркуаду підтвердити безпеку його королівства, перевіривши, що кожна вежа досяжна з будь-якої іншої в мережі Дюлока?

Вхідні дані

У першому рядку задано одне ціле число $n$ — кількість веж в кололівстві Дюлок.

Після зчитування числа починається взаємодія. Ви можете робити запити вигляду: "? s" (без лапок), де $s$ — це бінарний рядок довжини $n$, такий що символ $s_i$ є 1 якщо $i \in S$ і 0 в іншому випадку. Після запиту, зчитайте одне число — відповідь на ваш запит.

Вихідні дані

Коли ви визначите чи $G$ є зв’язним чи ні, виведіть відповідь у форматі: "! x" (без лапок), де $x$ це 1 якщо $G$ є зв’язним і 0 в іншому випадку.

Обмеження

$1 \leq |V| \leq 200$.

Ви можете зробити не більше ніж 3500 запитів.

Примітки

У першому прикладі, $|V| = 4$, $G = (V, E)$, $V = \{1, 2, 3, 4\}$, $E = \{(1, 2), (2, 3), (3, 4), (2, 4)\}$.

Input	Output	Description
4		Дано $|V|$.
	? 1100	Запит про підмножину $\{1, 2\}$.
2		Відповідь журі 2.
	? 0010	Запит про підмножину $\{3\}$.
2		Відповідь журі 2.
	? 1001	Запит про підмножину $\{1, 4\}$.
2		Відповідь журі 2.
	! 1	Алгоритм виявив, що G є зв’язним.

У другому прикладі, $|V| = 2$, $G = (V, E)$, $V = \{1, 2\}$, $E = \emptyset$.

Input	Output	Description
2		Дано $|V|$.
	? 10	Запит про підмножину $\{1\}$.
0		Відповідь журі 0.
	? 11	Запит про підмножину $\{1, 2\}$.
0		Відповідь журі 0.
	! 0	Алгоритм виявив, що G не є зв’язним.