Un village de Bajtocja est en cours de modernisation. L'objectif du dernier projet gouvernemental est de fournir des ordinateurs aux habitants des villages et petites villes qui n'en possèdent pas. Bajtazar supervise la modernisation de l'un des villages inclus dans le programme – Bajtoszyce – où, pour l'instant, aucun habitant ne possède d'ordinateur.

À Bajtoszyce vivent $n$ habitants, que Bajtazar a numérotés de $1$ à $n$ pour faciliter les choses. Au début, aucun habitant ne possède d'ordinateur. La tâche de Bajtazar consiste à traiter des événements de trois types :

• $+ \ a_i \ b_i$ – Un ordinateur est livré à un habitant de Bajtoszyce. Bajtazar ne sait cependant pas si l'ordinateur a été livré à l'habitant numéro $a_i$ ou $b_i$. Il peut arriver que $a_i = b_i$ – dans ce cas, l'ordinateur a certainement été livré à l'habitant numéro $a_i$. Il est certain que l'ordinateur est livré à un habitant qui n'en possède pas actuellement.
• $- \ c_i$ – L'ordinateur de l'habitant numéro $c_i$ tombe en panne. Il est certain que cet habitant possédait un ordinateur jusqu'à présent (mais il ne l'aura plus, il pourra donc en recevoir un nouveau à l'avenir).
• $? \ d_i$ – Bajtazar doit déterminer (en utilisant toutes les informations dont il dispose jusqu'à présent) si l'habitant numéro $d_i$ : possède certainement un ordinateur, ne possède certainement pas d'ordinateur, ou s'il est impossible de savoir s'il possède un ordinateur.

Écrivez un programme qui aidera Bajtazar à répondre aux questions qui lui sont posées !

Entrée

La première ligne de l'entrée contient deux entiers $n$ et $q$ ($1 \le n \le 300\,000$ ; $1 \le q \le 1\,000\,000$), représentant respectivement le nombre d'habitants de Bajtoszyce et le nombre d'événements que Bajtazar doit traiter.

Les $q$ lignes suivantes contiennent les descriptions des événements successifs décrits dans l'énoncé. Dans tous les événements, on a $1 \le a_i, b_i, c_i, d_i \le n$.

Il est garanti que Bajtazar sera interrogé au moins une fois sur son état de connaissance, c'est-à-dire que l'entrée contient au moins un événement de type '?'. Il est également garanti qu'il existe au moins un scénario de livraison d'ordinateurs dans lequel l'ordinateur est toujours reçu par une personne qui n'en possède pas actuellement, et dans lequel l'ordinateur tombe toujours en panne chez une personne qui en possède un actuellement.

Sortie

La sortie doit contenir une chaîne de caractères d'une longueur égale au nombre d'événements de type '?'. Si, lors de la $i$-ième requête, l'habitant possède certainement un ordinateur, le $i$-ième caractère de cette chaîne doit être '1'. Si cet habitant ne possède certainement pas d'ordinateur, le $i$-ième caractère doit être '0'. Si cet habitant peut, mais ne doit pas nécessairement posséder un ordinateur, le $i$-ième caractère doit être '?'.

Exemples

Entrée 1

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

Sortie 1

0?1011

Remarque 1

Au début, personne ne possède d'ordinateur, donc la réponse à la première question est négative, et le premier caractère de la sortie est '0'. Ensuite, deux ordinateurs sont livrés et nous sommes interrogés pour savoir si le deuxième habitant possède un ordinateur. Il est possible que l'une des deux livraisons précédentes lui ait été destinée, mais il est aussi possible que les ordinateurs aient été livrés respectivement au premier et au troisième habitant. Nous ne sommes donc pas en mesure de déterminer sans équivoque si le deuxième habitant possède un ordinateur, la réponse est donc '?'. Notez qu'après la livraison suivante, il devient clair que le deuxième habitant devait déjà posséder un ordinateur, mais au moment de la question, Bajtazar ne pouvait pas le savoir.