Это интерактивная задача.

Под непосредственным наблюдением Kanako и Moriya железнодорожная система Gensokyo наконец-то завершена. GSKR (Gensokyo Railways) состоит из $$$n$$$ станций с $$$m$$$ двунаправленными дорожками, соединяющими их. $$$i$$$-я дорожка имеет длину $$$l_i$$$ ($$$1\le l_i\le 10^6$$$). Из-за бюджетных ограничений железнодорожная система может быть не связной, хотя между двумя станциями может быть более одного пути.

Значение железнодорожной системы определяется как общая длина всех ее дорожек. Максимальная (или минимальная) мощность железнодорожной системы определяется как максимальное (или минимальное) значение среди всех полных остовных лесов.

Полный остовный лес графа — это остовный лес с той же связностью, что и данный граф.

У Kanako есть симулятор, способный обрабатывать не более $$$2m$$$ запросов. На вход симулятора подается строка $$$s$$$ длины $$$m$$$, состоящая из символов 0 и/или 1. Симулятор оставит $$$i$$$-ю дорожку, если $$$s_i=$$$ 1. Затем устройство сообщит Kanako максимальную мощность системы в смоделированном состоянии.

Kanako хочет узнать минимальную мощность системы со всеми дорожками с помощью симулятора.

Структура железнодорожной системы определяется заранее. Другими словами, интерактор не адаптивен.

Начните взаимодействие, прочитав $$$n,m$$$.

Чтобы сделать запрос, выведите «? $$$s$$$» (без кавычек, $$$s$$$ — это строка длины $$$m$$$, состоящая из символов 0 и/или 1 ). Затем вы должны прочитать наш ответ из стандартного ввода — максимальная мощность системы в смоделированном состоянии.

Если ваша программа сделала недопустимый запрос или закончились попытки, интерактор немедленно завершится, и ваша программа получит вердикт Неверный ответ.

Чтобы дать окончательный ответ, выведите «! $$$L$$$» (без кавычек, $$$L$$$ — это минимальная мощность системы со всеми дорожками). Обратите внимание, что предоставление этого ответа не считается как один из $$$2m$$$ запросов.

После печати запроса не забудьте вывести конец строки и очистить вывод. В противном случае вы получите превышение лимита бездействия. Для этого используйте:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Паскале;
• stdout.flush() в Python;
• см. документацию для других языков.

Взломы

Первая строка ввода должна содержать два целых числа $$$n,m$$$ ($$$2 \leq n \leq 200$$$, $$$1\le m \le 500$$$) — количество станций и путей.

Следующие $$$m$$$ строк должны содержать ровно $$$3$$$ целых чисел через пробел $$$u_i$$$, $$$v_i$$$, $$$l_i$$$ ($$$1\le u_i,v_i \le n$$$, $$$u_i\ne v_i$$$, $$$1 \leq l_i \leq 10^6$$$) — вершины ребра и длина $$$i$$$-й дорожки.