The village of Bajtocja is undergoing modernization. The goal of the latest government project is to provide computers to those residents of villages and small towns who do not have them. Bajtazar is overseeing the modernization of one of the villages covered by the program – Bajtoszyce – where currently no resident owns a computer.

There are $n$ residents in Bajtoszyce, whom Bajtazar has numbered with integers from $1$ to $n$ for convenience. Initially, no resident has a computer. Bajtazar's task is to process events of three types:

• $+ \ a_i \ b_i$ – A computer is delivered to a resident of Bajtoszyce. However, Bajtazar does not know whether the computer was delivered to the resident numbered $a_i$ or $b_i$. It may happen that $a_i = b_i$ – in that case, the computer was definitely delivered to the resident numbered $a_i$. It is certain that the computer is delivered to a resident who does not currently own one.
• $- \ c_i$ – The computer of the resident numbered $c_i$ breaks down. It is certain that this resident owned a computer until now (but will no longer have one, so they may receive a new one in the future).
• $? \ d_i$ – Bajtazar must determine (using all the knowledge provided to him so far) whether the resident numbered $d_i$: definitely owns a computer, definitely does not own a computer, or if it is unknown whether they own a computer.

Write a program that will help Bajtazar answer the questions asked of him!

Input

The first line of input contains two integers $n$ and $q$ ($1 \le n \le 300\,000$; $1 \le q \le 1\,000\,000$), representing the number of residents of Bajtoszyce and the number of events that Bajtazar must process, respectively.

The next $q$ lines contain descriptions of subsequent events as described in the problem statement. In all events, $1 \le a_i, b_i, c_i, d_i \le n$.

It is guaranteed that Bajtazar will be asked about his state of knowledge at least once, i.e., the input contains at least one event of type '?'. It is also guaranteed that there exists at least one sequence of computer deliveries where the computer is always received by a person who does not currently own one, and where the computer always breaks down for a person who currently owns one.

Output

The output should be a string of characters with a length equal to the number of '?' events. If, at the $i$-th query, the resident definitely owns a computer, the $i$-th character in this string should be '1'. If this resident definitely does not own a computer, the $i$-th character in this string should be '0'. If this resident may or may not own a computer, the $i$-th character in this string should be '?'.

Examples

Input 1

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

Output 1

0?1011

Note

Explanation of the example: Initially, no one owns a computer, so the answer to the first question is negative, and the first character in the output is '0'. Then two computers are delivered, and we are asked whether the second resident owns a computer. It is possible that one of the two deliveries so far was to them, but it could also have happened that the computers were delivered to the first and third residents, respectively. We are therefore unable to definitively state whether the second resident owns a computer, so the answer is '?'. Note that after the next delivery, it becomes clear that the second resident must have already owned a computer, but at the time of the query, Bajtazar could not have known this.