题目描述

在晚秋时分观赏 L 国举世闻名的佳景——藏雾山，无不是一件惬意之事。

藏雾山共有 $n$ 座山峰，从 $1$ 到 $n$ 编号。起初，$n$ 座山峰的山顶均被秋雾遮盖，因而无法辨别其高度。

同时，称第 $i$ 座山峰为间峰，当且仅当其高度恰好是第 $i-1$ 座与第 $i + 1$ 座高度的平均值（特别地，第 $1$ 座与第 $n$ 座不算间峰）。藏雾山一带向来会在部分间峰的山底悬挂旗帜，起初所有山峰的山底均无旗帜。

现有 $m$ 天，每天会发生以下之一的事件：

• 雾去/雾回：第 $x$ 座山峰山顶的秋雾散去，或重新聚集。
• 旗升/旗落：第 $x$ 座山峰山底的旗帜挂起，或被人卸下。
• 来客：一位登山爱好者造访藏雾山欲攀登第 $x$ 座山峰，他希望能当天知晓该山峰的海拔高度。

登山爱好者们将以两种方式知晓：直接观测出未被秋雾遮盖山峰的海拔高度，或是利用当天各山底旗帜给出的间峰信息，尽可能地推算出其余山峰的高度。除此之外，他们无法使用其他方式，包括但不限于与过往的来客交流分享信息等。

你能求出每位登山爱好者能否知晓目标山峰的高度吗？

输入格式

第一行包含两个正整数 $n$ 和 $m$，分别为藏雾山的山峰个数和事件持续的天数。

接下来 $m$ 行，每行包含两个正整数 $op, x$，其中 $op \in \{1,2,3\}$，具体地：

• 对于 $op=1$，保证 $1 \le x \le n$，表示若第 $x$ 座山峰的山顶有雾，则变为无雾状态；若第 $x$ 座山峰的山顶无雾，则变为有雾状态。
• 对于 $op=2$，保证 $2 \le x < n$，表示若第 $x$ 座山峰的山底无旗，则变为有旗状态；若第 $x$ 座山峰的山底有旗，则变为无旗状态。
• 对于 $op=3$，保证 $1 \le x \le n$，表示一位欲攀登第 $x$ 座山峰的登山爱好者造访。

输出格式

输出若干行，每行一个布尔值依次表示每位登山爱好者能否知晓高度，$1$ 则能，$0$ 则不能。

3 5
1 1
1 3
3 2
2 2
3 2

0
1

5 6
1 1
1 3
2 2
2 3
2 4
3 5

1

提示

【样例解释 #1】

在没有任何间峰信息的情况下，第一个登山爱好者不可能知晓被秋雾遮盖山峰的高度。

第二个登山爱好者造访时已知山峰 $1$ 的高度、山峰 $3$ 的高度以及山峰 $2$ 为间峰，因此山峰 $2$ 的高度能通过平均值计算得到。

【数据规模与约定】

本题采用捆绑测试。你必须通过 Subtask 中所有的测试点才能获得该 Subtask 的分数。

• Subtask #1 (7 points)：$n \le 5$，$m \le 10$。
• Subtask #2 (13 points)：$n,m \le 100$。
• Subtask #3 (15 points)：$n,m \le 2000$。
• Subtask #4 (20 points)：$n,m \le 10^5$。
• Subtask #5 (20 points)：所有 $op = 1$ 事件在所有 $op = 2$ 事件后。
• Subtask #6 (25 points)：无特殊限制。

对于所有的数据，保证 $3 \le n \le 5 \cdot 10^5$，$1 \le m \le 5 \cdot 10^5$。