Bajtocka 村正在进行现代化改造。政府最新项目的目标是为那些没有电脑的村民和城镇居民提供电脑。Bajtazar 负责监督其中一个参与该项目的村庄——Bajtoszyce，目前该村没有任何居民拥有电脑。

Bajtoszyce 有 $n$ 名居民，Bajtazar 为了方便起见，将他们编号为 $1$ 到 $n$。起初，没有任何居民拥有电脑。Bajtazar 的任务是处理以下三种类型的事件：

• $+ \ a_i \ b_i$ —— 一台电脑被送往 Bajtoszyce 的居民处。然而，Bajtazar 不知道电脑是送给了编号为 $a_i$ 的居民还是 $b_i$ 的居民。可能出现 $a_i = b_i$ 的情况，此时电脑肯定送给了编号为 $a_i$ 的居民。可以确定的是，电脑被送给了一位当前没有电脑的居民。
• $- \ c_i$ —— 编号为 $c_i$ 的居民的电脑坏了。可以确定的是，该居民此前拥有电脑（但现在不再拥有，因此未来可能会收到新电脑）。
• $? \ d_i$ —— Bajtazar 必须（利用他目前掌握的所有信息）判断编号为 $d_i$ 的居民：肯定拥有电脑、肯定没有电脑，还是无法确定是否拥有电脑。

请编写一个程序，帮助 Bajtazar 回答这些问题！

输入格式

输入的第一行包含两个整数 $n$ 和 $q$ ($1 \le n \le 300\,000; 1 \le q \le 1\,000\,000$)，分别表示 Bajtoszyce 的居民人数和 Bajtazar 需要处理的事件数量。

接下来的 $q$ 行包含题目描述中提到的事件描述。在所有事件中，满足 $1 \le a_i, b_i, c_i, d_i \le n$。

保证 Bajtazar 至少会被询问一次他的知识状态，即输入中至少包含一个类型为 ‘?’ 的事件。同时保证至少存在一种电脑分配过程，使得电脑总是被送给当前没有电脑的人，且电脑总是坏在当前拥有电脑的人手中。

输出格式

输出应为一个长度等于 ‘?’ 事件数量的字符串。如果第 $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

说明 1

起初没有人拥有电脑，因此第一个问题的回答是否定的，输出的第一个字符是 ‘0’。随后送出了两台电脑，我们被问及第二位居民是否拥有电脑。有可能这两次交付中其中一次是给他的，但也可能电脑分别送给了第一位和第三位居民。因此，我们无法明确判断第二位居民是否拥有电脑，所以回答是 ‘?’。请注意，在下一次交付后，情况会变得明朗，即第二位居民当时一定已经拥有了电脑，但在询问时 Bajtazar 无法得知这一点。