El pueblo de Bajtocka está pasando por un proceso de modernización. El objetivo del nuevo proyecto gubernamental es proporcionar computadoras a aquellos habitantes de pueblos y pequeñas ciudades que no poseen una. Bajtazar supervisa la modernización de uno de los pueblos incluidos en el programa, Bajtoszyce, donde actualmente ningún habitante tiene una computadora.

En Bajtoszyce viven $n$ habitantes, a quienes Bajtazar ha numerado convenientemente con números enteros del $1$ al $n$. Al principio, ninguno de los habitantes tiene una computadora. La tarea de Bajtazar es procesar eventos de tres tipos:

• $+ \ a_i \ b_i$ – Se entrega una computadora a un habitante de Bajtoszyce. Sin embargo, Bajtazar no sabe si la computadora se entregó al habitante con el número $a_i$ o al $b_i$. Puede ocurrir que $a_i = b_i$, en cuyo caso la computadora fue entregada con seguridad al habitante con el número $a_i$. Es seguro que la computadora se entrega a un habitante que actualmente no posee una.
• $- \ c_i$ – La computadora del habitante con el número $c_i$ se avería. Es seguro que este habitante poseía una computadora hasta ese momento (pero ahora ya no la tendrá, por lo que podría recibir una nueva en el futuro).
• $? \ d_i$ – Bajtazar debe determinar (utilizando toda la información proporcionada hasta el momento) si el habitante con el número $d_i$: definitivamente posee una computadora, definitivamente no posee una computadora, o si no se sabe si posee una computadora.

¡Escribe un programa que ayude a Bajtazar a responder las preguntas que se le plantean!

Entrada

La primera línea de la entrada contiene dos números enteros $n$ y $q$ ($1 \le n \le 300\,000$; $1 \le q \le 1\,000\,000$), que representan el número de habitantes de Bajtoszyce y el número de eventos que Bajtazar debe procesar, respectivamente.

En las siguientes $q$ líneas se encuentran las descripciones de los eventos sucesivos descritos en el enunciado. En todos los eventos se cumple que $1 \le a_i, b_i, c_i, d_i \le n$.

Se garantiza que a Bajtazar se le preguntará al menos una vez sobre su estado de conocimiento, es decir, la entrada contiene al menos un evento de tipo '?'. También se garantiza que existe al menos una secuencia de entrega de computadoras en la que la computadora siempre es recibida por una persona que actualmente no posee una, y en la que la computadora siempre se avería a una persona que actualmente posee una.

Salida

La salida debe consistir en una cadena de caracteres con una longitud igual al número de eventos de tipo '?'. Si en la $i$-ésima consulta el habitante definitivamente posee una computadora, el $i$-ésimo carácter en la cadena debe ser '1'. Si el habitante definitivamente no posee una computadora, el $i$-ésimo carácter debe ser '0'. Si el habitante puede, pero no necesariamente posee una computadora, el $i$-ésimo carácter debe ser '?'.

Ejemplos

Entrada 1

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

Salida 1

0?1011

Nota 1

Al principio nadie tiene una computadora, por lo que la respuesta a la primera pregunta es negativa y el primer carácter en la salida es '0'. Luego se entregan dos computadoras y se nos pregunta si el segundo habitante posee una computadora. Es posible que una de las dos entregas anteriores haya sido para él, pero también pudo haber ocurrido que las computadoras fueran entregadas al primer y tercer habitante, respectivamente. Por lo tanto, no podemos determinar inequívocamente si el segundo habitante posee una computadora, por lo que la respuesta es '?'. Ten en cuenta que después de la siguiente entrega, quedará claro que el segundo habitante ya debía poseer una computadora, sin embargo, en el momento de la consulta, Bajtazar no podía saberlo.