无向图中的锯齿交替环（zigzag cycle）是指一个顶点序列 $a_0, a_1, \dots, a_{k-1}$（顶点不一定两两不同），满足对于所有 $i : 0 \le i < k$，$a_i$ 和 $a_{(i+1) \bmod k}$ 在图中相邻，且满足以下条件之一：

1. $a_{(i+k-1) \bmod k} < a_i$ 且 $a_i > a_{(i+1) \bmod k}$
2. $a_{(i+k-1) \bmod k} > a_i$ 且 $a_i < a_{(i+1) \bmod k}$

如果恰好存在 $p$ 个不同的 $i : 0 \le i < k$ 满足 $a_i = u, a_{(i+1) \bmod k} = v$ 或 $a_i = v, a_{(i+1) \bmod k} = u$，则称该环包含边 $(u, v)$ $p$ 次。

如果存在一个锯齿交替环的集合，使得图中的每条边都恰好被其中一个环包含 $1$ 次，而被其余所有环包含 $0$ 次（即：你可以将图的边集划分为若干个锯齿交替环），则称该图是可拆分的（splittable）。

给定一个初始为空的图。请处理以下类型的查询：

1. 在顶点 $u$ 和 $v$ 之间添加一条边。
2. 移除顶点 $u$ 和 $v$ 之间的一条边。

在每次查询后，输出该图是否是可拆分的。

输入格式

第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 3 \cdot 10^5$，$1 \le q \le 3 \cdot 10^5$），分别表示图中的顶点数和查询次数。

接下来的 $q$ 行，每行包含三个整数 $t, u, v$（$t \in \{1, 2\}$，$1 \le u < v \le n$），表示查询的类型以及边的两个端点。如果 $t = 1$，则需要添加该边；如果 $t = 2$，则需要移除该边。保证不会要求添加一条已经存在的边，也不会要求删除一条不存在的边。

输出格式

输出 $q$ 行。第 $i$ 行在第 $i$ 次查询后图是可拆分时输出 $1$，否则输出 $0$。

样例

输入格式 1

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

输出格式 1

0
0
0
0
1
0
0
0
0
1

说明

在处理完所有查询后，一种可能的锯齿交替环集合为 $\{[1, 4, 3, 5], [2, 6, 4, 5]\}$。