{"raw_statement":[{"iden":"background","content":"PA 2024 1A"},{"iden":"statement","content":"**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 1 [Modernizacja Bajtocji](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/mod/)**\n\nByteland 正在走向现代化。最新的政府项目旨在为那些没有电脑的村镇居民提供电脑。Byteasar 正在监督该计划中的一个村庄——Bytetown——的现代化进程，目前那里没有一个居民拥有电脑。\n\nBytetown 有 $n$ 个居民，为了简单起见，Byteasar 将他们用 $1$ 到 $n$ 的整数编号。最初没有一个居民拥有电脑。Byteasar 的任务是处理三种形式的事件：\n\n- $\\texttt{+}\\ a_i\\ b_i$：将一台电脑送给 Bytetown 的居民。然而，Byteasar 并不知道电脑是送给了编号为 $a_i$ 还是 $b_i$ 的居民。可能会出现 $a_i = b_i$ 的情况——在这种情况下，电脑肯定送给了编号为 $a_i$ 的居民。可以确定的是，电脑被送到了目前还没有电脑的居民手中。\n- $\\texttt{-}\\ c_i$：编号为 $c_i$ 的居民的电脑坏了。可以肯定的是，该居民曾经拥有一台电脑（但现在不再拥有，因此将来可能会收到一台新电脑）。\n- $\\texttt{?}\\ d_i$：Byteasar 需要（利用**迄今为止**获得的所有信息）确定编号为 $d_i$ 的居民：肯定有电脑，肯定没有电脑，还是不确定他是否有电脑。\n\n请编写一个程序，帮助 Byteasar 回答所提出的问题！\n\n注：在居民的电脑坏掉的前一刻，Byteasar 不一定可以确定这个居民是否有电脑。换句话说，在某居民电脑坏掉之前，不一定可以从之前的事件中确定他是否有电脑。"},{"iden":"input","content":"第一行包含两个整数 $n$ 和 $q\\ (1\\le n\\le 300\\, 000, 1\\le q\\le 1\\,000\\,000)$，分别表示 Bytetown 的居民人数和 Byteasar 需要处理的事件数量。\n\n接下来的 $q$ 行描述了题目中的连续发生的事件。在所有事件中，$1 \\le a_i,b_i,c_i,d_i \\le n$。\n\n保证 Byteasar 至少会被问及一次他知道的内容，即输入中至少包含一个 `?`，还保证至少有一次电脑送出过程，在这个过程中，电脑总会给一个目前不拥有电脑的人，且保证对于电脑坏掉事件中的居民，电脑坏掉时总会拥有一台电脑。"},{"iden":"output","content":"输出一个字符串，其长度等于 `?` 事件的个数。如果在第 $i$ 次查询时，该居民肯定有电脑，则该字符串中的第 $i$ 个字符为 `1`。如果该居民肯定没有电脑，则该字符串中的第 $i$ 个字符应为 `0`。如果不能确定该居民是否拥有电脑，则该序列中的第 $i$ 个字符应为 `?`。"},{"iden":"note","content":"最初没有人有电脑，所以第一个询问的答案为「否」，输出的第一个字符是 `0`。然后送出了两台电脑，我们又被问到另一位居民是否有电脑。有可能迄今为止送出的两台电脑中有一台是送给他的，但也有可能电脑是分别送给第一位和第三位居民的。因此，我们无法最终确定第二位居民是否有电脑，所以答案是 `?`。需要注意的是，在下一次送出之后，第二位居民肯定已经拥有了一台电脑，但在询问 Byteasar 时，他并不知道这一点。"}],"translated_statement":null,"sample_group":[["5 11\n? 1\n+ 1 2\n+ 2 3\n? 2\n+ 3 1\n- 2\n? 1\n? 2\n? 3\n+ 2 2\n? 2\n","0?1011\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}