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

Обмеження: 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 не є зв’язним.