Làng Bajtocja đang trải qua quá trình hiện đại hóa. Mục tiêu của dự án chính phủ mới nhất là cung cấp máy tính cho những cư dân ở các ngôi làng và thị trấn nhỏ chưa có máy tính. Bajtazar giám sát việc hiện đại hóa một trong những ngôi làng thuộc chương trình – Bajtoszyce – nơi hiện tại không có cư dân nào sở hữu máy tính.

Tại Bajtoszyce có $n$ cư dân, được Bajtazar đánh số từ $1$ đến $n$ để thuận tiện. Ban đầu, không ai trong số họ có máy tính. Nhiệm vụ của Bajtazar là xử lý các sự kiện thuộc ba loại sau:

• $+ \ a_i \ b_i$ – Một chiếc máy tính được cung cấp cho một cư dân của Bajtoszyce. Tuy nhiên, Bajtazar không biết chắc máy tính được cung cấp cho cư dân có số hiệu $a_i$ hay $b_i$. Có thể xảy ra trường hợp $a_i = b_i$ – khi đó máy tính chắc chắn được cung cấp cho cư dân có số hiệu $a_i$. Điều chắc chắn là máy tính luôn được cung cấp cho một cư dân hiện chưa có máy tính.
• $- \ c_i$ – Máy tính của cư dân có số hiệu $c_i$ bị hỏng. Điều chắc chắn là cư dân này trước đó đã có máy tính (nhưng bây giờ sẽ không còn nữa, vì vậy trong tương lai họ có thể nhận được máy tính mới).
• $? \ d_i$ – Bajtazar phải xác định (dựa trên tất cả thông tin đã có cho đến thời điểm hiện tại) liệu cư dân có số hiệu $d_i$: chắc chắn có máy tính, chắc chắn không có máy tính, hay không thể xác định được liệu họ có máy tính hay không.

Hãy viết chương trình giúp Bajtazar trả lời các câu hỏi của mình!

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $n$ và $q$ ($1 \le n \le 300\,000$; $1 \le q \le 1\,000\,000$), lần lượt là số lượng cư dân của Bajtoszyce và số lượng sự kiện mà Bajtazar phải xử lý.

Trong $q$ dòng tiếp theo là mô tả các sự kiện như đã nêu trong đề bài. Trong tất cả các sự kiện, $1 \le a_i, b_i, c_i, d_i \le n$.

Đảm bảo rằng Bajtazar sẽ được hỏi về trạng thái kiến thức của mình ít nhất một lần, nghĩa là dữ liệu vào chứa ít nhất một sự kiện loại '?'. Cũng đảm bảo rằng luôn tồn tại ít nhất một quá trình cung cấp máy tính mà trong đó máy tính luôn được trao cho người hiện chưa có nó, và máy tính luôn bị hỏng ở người hiện đang sở hữu nó.

Dữ liệu ra

Dữ liệu ra phải là một chuỗi ký tự có độ dài bằng số lượng sự kiện loại '?'. Nếu tại câu hỏi thứ $i$, cư dân đó chắc chắn có máy tính, ký tự thứ $i$ trong chuỗi phải là '1'. Nếu cư dân đó chắc chắn không có máy tính, ký tự thứ $i$ phải là '0'. Nếu cư dân đó có thể có hoặc không có máy tính, ký tự thứ $i$ phải là '?'.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

0?1011

Ghi chú

Giải thích ví dụ: Ban đầu không ai có máy tính, vì vậy câu trả lời cho câu hỏi đầu tiên là phủ định, và ký tự đầu tiên trên đầu ra là '0'. Sau đó, hai máy tính được cung cấp và chúng ta được hỏi liệu cư dân thứ hai có máy tính hay không. Có khả năng một trong hai lần cung cấp trước đó là dành cho người này, nhưng cũng có thể các máy tính đã được cung cấp cho cư dân thứ nhất và thứ ba. Do đó, chúng ta không thể khẳng định chắc chắn liệu cư dân thứ hai có máy tính hay không, vì vậy câu trả lời là '?'. Lưu ý rằng sau lần cung cấp tiếp theo, sẽ trở nên rõ ràng rằng cư dân thứ hai chắc chắn đã có máy tính, tuy nhiên tại thời điểm đặt câu hỏi, Bajtazar không thể biết được điều đó.