バイトックの村では近代化が進んでいます。最新の政府プロジェクトの目的は、コンピュータを所有していない村や小さな町の住民にコンピュータを支給することです。バイタザールは、このプログラムの対象となっている村の一つであるバイトシツェの近代化を監督しています。現在、この村の住民は誰もコンピュータを所有していません。
バイトシツェには $n$ 人の住民が住んでおり、バイタザールは便宜上、彼らに $1$ から $n$ までの整数で番号を振りました。当初、住民は誰もコンピュータを持っていません。バイタザールの仕事は、以下の3種類のイベントを処理することです。
- $+ \ a_i \ b_i$ – バイトシツェの住民にコンピュータが1台支給されます。しかし、バイタザールはコンピュータが住民 $a_i$ に支給されたのか、それとも $b_i$ に支給されたのかを知りません。$a_i = b_i$ となる場合もあり、その場合はコンピュータが確実に住民 $a_i$ に支給されたことになります。コンピュータは、現在コンピュータを所有していない住民に確実に支給されることが保証されています。
- $- \ c_i$ – 住民 $c_i$ のコンピュータが故障します。この住民はそれまでコンピュータを所有していたことが確実です（ただし、故障した後は所有しなくなるため、将来的に新しいコンピュータを受け取る可能性があります）。
- $? \ d_i$ – バイタザールは（これまでに得られたすべての知識を用いて）、住民 $d_i$ がコンピュータを確実に所有しているか、確実に所有していないか、あるいは所有しているかどうかが不明であるかを判断しなければなりません。
バイタザールが質問に答えるのを助けるプログラムを作成してください。
入力
入力の最初の行には、2つの整数 $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$ が成り立ちます。
バイタザールが少なくとも一度は自身の知識状態について質問されること、つまり入力には少なくとも1つの '?' 型のイベントが含まれることが保証されています。また、コンピュータを現在所有していない人が常にコンピュータを受け取り、コンピュータを現在所有している人のコンピュータが常に故障するという、コンピュータ支給の過程が少なくとも1つ存在することが保証されています。
出力
出力には、'?' 型のイベントの数と同じ長さの文字列が含まれるべきです。$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' です。次に2台のコンピュータが支給され、2番目の住民がコンピュータを所有しているかどうかが問われます。これまでの2回の支給のうち一方が彼に対するものだった可能性もありますが、1番目と3番目の住民がそれぞれコンピュータを受け取った可能性もあります。したがって、2番目の住民がコンピュータを所有しているかどうかを明確に判断することはできず、答えは '?' となります。次の支給の後には、2番目の住民がすでにコンピュータを所有していなければならなかったことが明らかになりますが、質問の時点ではバイタザールはそれを知ることができなかったことに注意してください。