markdown

E. 体育课

时间限制：每个测试点 $1$ 秒
内存限制：每个测试点 $256$ MB
输入：标准输入
输出：标准输出

今年 Alex 中学毕业，成为了 Berland 国立大学的一名大一新生。令他十分惊讶的是，尽管他学的是编程，却仍然要上体育课。学期很快就要结束了，但不幸的是，Alex 至今一节课都没上过！

由于 Alex 不想被开除，他想知道学期结束前还剩多少个工作日，这样他就可以在这些天去上体育课。然而，在 BSU，计算工作日数量是一件复杂的事情：

学期结束前还有 $n$ 天（编号从 $1$ 到 $n$），最初所有天都是工作日。接着，学校工作人员依次发布 $q$ 条指令，每条指令由三个数字 $l$、$r$ 和 $k$ 描述：

• 如果 $k = 1$，那么从第 $l$ 天到第 $r$ 天（包含两端）全部变为非工作日。即使其中某些天之前被之前的指令设为工作日，这些天仍然变为非工作日；
• 如果 $k = 2$，那么从第 $l$ 天到第 $r$ 天（包含两端）全部变为工作日。即使其中某些天之前被之前的指令设为非工作日，这些天仍然变为工作日。

请帮助 Alex 在每条指令之后，确定剩余的工作日数量。

输入

第一行包含一个整数 $n$，第二行包含一个整数 $q$（$1 \le n \le 10^9$，$1 \le q \le 3 \cdot 10^5$）——分别表示学期结束前剩余的天数和指令的数量。

接下来 $q$ 行，第 $i$ 行包含三个整数 $l_i$、$r_i$ 和 $k_i$，表示第 $i$ 条指令（$1 \le l_i \le r_i \le n$，$1 \le k_i \le 2$）。

输出

输出 $q$ 个整数。第 $i$ 个整数应等于前 $i$ 条指令发布后，学期结束前剩余的工作日数量。

样例

输入

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

输出

2
0
2
3
1
4