给你一个 $N \times N$ 的网格。第 $i$ 行第 $j$ 列的单元格记为 $(i, j)$。最初，网格中的每个单元格都被染成白色。

我们将使用 $2N - 2$ 次操作对网格进行染色。第 $i$ 次操作记为 $(d_i, x_i, c_i)$。格式为 $(d, x, c)$ 的操作表示以下内容：

• 对于 $d = 0$，我们对第 $x$ 列的单元格进行染色。对于 $d = 1$，我们对第 $x$ 行的单元格进行染色。
• 对于 $c = 0$，我们将该列/行染成白色。对于 $c = 1$，我们将该列/行染成黑色。

保证如果按顺序执行这些操作，第 $2, 3, 4, \dots, N$ 行中的每一行都将按此顺序被恰好染色一次，且第 $2, 3, 4, \dots, N$ 列中的每一列也将按此顺序被恰好染色一次。注意，没有任何操作会给第一行和第一列染色。形式化地，满足以下条件：

• 对于所有满足 $0 \le i \le 1$ 且 $2 \le j \le N$ 的整数 $i, j$，存在唯一的整数 $1 \le k \le 2N - 2$ 使得 $(d_k, x_k) = (i, j)$。
• 对于所有满足 $1 \le i < j \le 2N - 2$ 且 $d_i = d_j$ 的整数 $i, j$，满足 $x_i < x_j$。

一个区域定义为相同颜色的相邻单元格的最大连通块，其中如果两个单元格共享一条边，则认为它们是相邻的。你需要求出在按给定顺序执行完这 $2N - 2$ 次操作后，区域的数量。

当然，这个问题太简单了，所以我们为你准备了 $Q$ 个询问！每个询问由 3 个整数 $(z, l, r)$ 表示。在每次询问后，你应该对于所有满足 $l \le x_i \le r$ 且 $d_i = z$ 的第 $i$ 次操作，将 $c_i$ 修改为 $1 - c_i$。然后，在修改后的操作序列下，你需要求出在执行完这 $2N - 2$ 次操作后区域的数量。注意，询问是累加的。

输入格式

第一行包含两个空格分隔的整数 $N$ 和 $Q$。

接下来的 $2N - 2$ 行中，第 $i$ 行包含三个空格分隔的整数 $d_i, x_i, c_i$。

接下来的 $Q$ 行中，第 $i$ 行包含三个空格分隔的整数 $z, l, r$，描述第 $i$ 个询问。

输出格式

对于每个询问，输出一行，包含一个整数，表示区域的数量。

数据范围

• $2 \le N, Q \le 2 \times 10^5$
• 对于每个操作，$0 \le d_i, c_i \le 1$ 且 $2 \le x_i \le N$
• 对于所有满足 $0 \le i \le 1$ 且 $2 \le j \le N$ 的整数 $i, j$，存在唯一的整数 $1 \le k \le 2N - 2$ 使得 $(d_k, x_k) = (i, j)$。
• 对于所有满足 $1 \le i < j \le 2N - 2$ 且 $d_i = d_j$ 的整数 $i, j$，满足 $x_i < x_j$。
• 对于每个询问，$0 \le z \le 1$ 且 $2 \le l \le r \le N$。

样例

输入样例 1

5 7
1 2 0
0 2 0
1 3 1
1 4 0
1 5 1
0 3 1
0 4 1
0 5 1
1 3 5
0 4 4
0 2 5
1 2 3
1 5 5
1 3 4
0 2 4

输出样例 1

3
5
5
5
5
6
4

输入样例 2

3 6
0 2 0
1 2 1
0 3 0
1 3 1
0 2 2
0 2 3
0 3 3
1 2 2
1 2 3
1 3 3

输出样例 2

3
2
2
2
2
2

说明

样例 2 中每次操作后网格的状态