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

Как хорошо известно, в городе «E» за его полутора тысячелетнюю историю ни разу не ремонтировали дороги. И только недавно руководство города отремонтировало некоторые из них.

Известно, что всего в городе «E» есть $$$n$$$ перекрестков и $$$m$$$ дорог, пронумерованных целыми числами от $$$1$$$ до $$$m$$$, перемещаться по которым можно в обе стороны. $$$i$$$-я дорога соединяет перекрестки с номерами $$$a_i$$$ и $$$b_i$$$.

Среди всех $$$m$$$ дорог было отремонтировано некоторое подмножество дорог, но вам не известно, какое именно. Единственная информация, которую вы смогли получить от дорожных служб города, это то, что от любого перекрестка можно доехать до любого другого, двигаясь только по отремонтированным дорогам.

Вы — молодой предприниматель, и решили организовать службу доставки свежего сырого мяса в городе «E» (в самом городе такое мясо называют «стейками», оно пользуется большой популярностью у местных жителей). Вы уже набрали штат курьеров, однако курьеры готовы перемещаться только по отремонтированным дорогам. Теперь вам предстоит выяснить, какие дороги уже отремонтированы.

Городская администрация предоставила вам город на некоторое время, поэтому вы можете делать различные действия одного из трех типов:

1. Заблокировать дорогу с номером $$$x$$$. В этом случае перемещение по дороге для курьеров будет запрещено. Исходно все дороги разблокированы.
2. Разблокировать дорогу с номером $$$x$$$. В этом случае курьеры смогут двигаться по дороге $$$x$$$, если она отремонтирована.
3. Попробовать доставить заказ на перекресток с номером $$$y$$$. В этом случае один из ваших курьеров начнет двигаться с неизвестного вам перекрестка $$$s$$$ и доставит заказ на перекресток с номером $$$y$$$ в том случае, если существует путь по разблокированным отремонтированным дорогам от перекрестка $$$s$$$ до перекрестка $$$y$$$. При этом гарантируется, что перекресток $$$s$$$ будет выбран заранее.

К сожалению, город предоставлен в ваше полное распоряжение ненадолго, поэтому вы можете сделать не более $$$100 \cdot m$$$ запросов.

После того, как вы считали описание набора входных данных, вы можете задавать запросы. Запросы могут быть трех типов:

1. «- $$$x$$$» ($$$1 \le x \le m$$$). В этом случае дорога с номером $$$x$$$ блокируется, если она ещё не была заблокирована.
2. «+ $$$x$$$» ($$$1 \le x \le m$$$). В этом случае дорога с номером $$$x$$$ разблокируется. Обратите внимание, что дорога $$$x$$$ должна быть заранее заблокирована. Исходно все дороги разблокированы.
3. «? $$$y$$$» ($$$1 \le y \le n$$$). В этом случае программа жюри выбирает некоторый город $$$s$$$. В случае, если от города $$$s$$$ до города $$$y$$$ можно добраться по разблокированным отремонтированным дорогам, программа жюри выведет $$$1$$$, иначе программа жюри выведет $$$0$$$. Обратите внимание, что город $$$s$$$ будет выбран до получения информации о городе $$$y$$$, однако при выборе города $$$s$$$ могут учитываться ваши предыдущие запросы.

Всего вы можете задать не более $$$100 \cdot m$$$ запросов для каждого набора входных данных.

После того, как вы нашли все отремонтированные дороги, выведите «! $$$c_1,\ c_2,\ c_3,\ \ldots,\ c_m$$$», где $$$c_i$$$ равно $$$1$$$, если дорога $$$i$$$ отремонтирована, и $$$0$$$, если дорога не отремонтирована. Этот вывод не будет считаться в общем числе запросов. На это программа жюри выведет $$$1$$$, если ваш ответ правильный, и $$$0$$$, если ответ не правильный. Если вы считали $$$0$$$, то ваша программа должна немедленно завершиться, чтобы получить вердикт Неправильный ответ. В противном случае вы можете получить любой вердикт, так как программа продолжит чтение из закрытого потока. Если вы считали $$$1$$$, то перейдите к следующему набору входных данных, или завершите программу, если такого нет.

Обратите внимание, что вам не обязательно разблокировать все дороги на момент вывода ответа. Гарантируется, что все отремонтированные дороги зафиксированы изначально и не будут меняться программой жюри в зависимости от запросов.

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

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

Взломы

Вы не можете делать взломы по этой задаче.