Деревня в Байтляндии проходит модернизацию. Целью новейшего правительственного проекта является предоставление компьютеров тем жителям деревень и малых городов, у которых их нет. Байтазар курирует модернизацию одной из деревень, участвующих в программе — Байтошице, — в которой в настоящее время ни у одного жителя нет компьютера.

В Байтошице проживает $n$ жителей, которых Байтазар для удобства пронумеровал целыми числами от $1$ до $n$. Изначально ни у кого из жителей нет компьютера. Задача Байтазара — обрабатывать события трех типов:

• $+ a_i \ b_i$ — Жителю Байтошице доставляется компьютер. Однако Байтазар не знает, был ли компьютер доставлен жителю с номером $a_i$ или $b_i$. Может случиться так, что $a_i = b_i$ — тогда компьютер точно был доставлен жителю с номером $a_i$. Известно, что компьютер всегда доставляется тому жителю, у которого его в данный момент нет.
• $- c_i$ — У жителя с номером $c_i$ ломается компьютер. Известно, что у этого жителя до этого момента был компьютер (но теперь его не будет, поэтому в будущем он может получить новый).
• $? \ d_i$ — Байтазар должен определить (используя всю имеющуюся у него на данный момент информацию), владеет ли житель с номером $d_i$ компьютером: точно владеет, точно не владеет, или же неизвестно, владеет ли он компьютером.

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

Входные данные

В первой строке входных данных находятся два целых числа $n$ и $q$ ($1 \le n \le 300\,000$; $1 \le q \le 1\,000\,000$), обозначающие количество жителей Байтошице и количество событий, которые должен обработать Байтазар.

В следующих $q$ строках содержатся описания событий, описанных в условии задачи. Во всех событиях выполняются условия $1 \le a_i, b_i, c_i, d_i \le n$.

Гарантируется, что Байтазара хотя бы раз спросят о его состоянии знаний, т.е. входные данные содержат хотя бы одно событие типа '?'. Также гарантируется, что существует хотя бы один сценарий доставки компьютеров, при котором компьютер всегда получает человек, у которого его в данный момент нет, и при котором компьютер всегда ломается у человека, у которого он в данный момент есть.

Выходные данные

На выходе должна быть строка символов длиной, равной количеству событий типа '?'. Если при $i$-м запросе житель точно владеет компьютером, то $i$-й символ в этой строке должен быть равен '1'. Если житель точно не владеет компьютером, то $i$-й символ должен быть равен '0'. Если житель может, но не обязан владеть компьютером, то $i$-й символ должен быть равен '?'.

Примеры

Пример 1

5 11
? 1
+ 1 2
+ 2 3
? 2
+ 3 1
- 2
? 1
? 2
? 3
+ 2 2
? 2

Выходные данные 1

0?1011

Примечание

В начале ни у кого нет компьютера, поэтому ответ на первый вопрос отрицательный, и первый символ на выходе — '0'. Затем доставляются два компьютера, и нас спрашивают, владеет ли второй житель компьютером. Возможно, что одна из двух доставок была ему, но могло случиться и так, что компьютеры получили первый и третий жители соответственно. Таким образом, мы не можем однозначно определить, владеет ли второй житель компьютером, поэтому ответ — '?'. Обратите внимание, что после следующей доставки станет ясно, что второй житель уже должен был владеть компьютером, однако в момент запроса Байтазар не мог этого знать.