题目描述

Alex 今年高中毕业，现在是 Berland 州立大学的一名大一新生。令他意外的是，尽管他学的是编程专业，但他仍然需要上体育课。学期即将结束，但 Alex 一节课都没有上过！

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

在学期结束前还剩 $n$ 天（编号从 $1$ 到 $n$），最开始所有天都是工作日。然后大学管理层会依次发布 $q$ 条通知，每条通知由三个数字 $l, r, k$ 组成：

• 如果 $k = 1$，那么从 $l$ 到 $r$ 的所有天（包括 $l$ 和 $r$）变为非工作日。如果这些天中有一些在之前的通知中被设为工作日，这些天仍然会变成非工作日；
• 如果 $k = 2$，那么从 $l$ 到 $r$ 的所有天（包括 $l$ 和 $r$）变为工作日。如果这些天中有一些在之前的通知中被设为非工作日，这些天仍然会变成工作日。

请你帮助 Alex 统计每发布完一条通知后还剩下多少个工作日。

输入格式

第一行包含一个整数 $n$。 第二行包含一个整数 $q$（$1 \le n \le 10^9$，$1 \le q \le 3 \times 10^5$）。

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

输出格式

输出 $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