今年Alex已经完成学业,现在是伯兰州立大学一年级的学生。对他来说,完全惊讶的是,尽管他学习编程,但他仍然必须参加体育课。学期快结束了,但不幸的是,Alex 仍然没有上任何课!
由于 Alex 不想被开除,他想知道到学期结束还剩多少工作日,这样他就可以在这些天里参加体育课。但在 BSU 计算工作日数是一件复杂的事情:
距离学期结束还剩n天(编号从1到n),最初都是工作日。随后,大学工作人员依次发布了q条命令。每个阶由三个数字 l、r 和 k 来表征:
- 如果 k = 1,则从 l 到 r(含)的所有日期都成为非工作日。如果其中一些日子被之前的某个订单设为工作日,那么这些日子仍然成为非工作日;
- 如果 k = 2,则从 l 到 r(含)的所有日期都成为工作日。如果其中一些日期被之前的某个订单设为非工作日,那么这些日期仍然会成为工作日。
帮助 Alex 确定每个订单后剩余的工作日数!
输入
第一行包含一个整数 n,第二行包含一个整数 q (1 ≤ n ≤ 109, 1 ≤ q ≤ 3·105) - 分别表示学期结束前剩余的天数和订单数。
接下来是 q 行,第 i 行包含三个整数 li、ri 和 ki,表示第 i 阶 (1 ≤ li ≤ ri ≤ n, 1 ≤ ki ≤ 2)。
输出
打印 q 个整数。其中第 i 个必须等于前 i 个订单发布后到期限结束为止剩余的工作日数。
示例
输入 #1
4 6 1 2 1 3 4 1 2 3 2 1 3 2 2 4 1 1 4 2
输出 #1
2 0 2 3 1 4