题目内容

现有一条带子，长度记作 $A$。开始的时候，带子上每个格子的颜色都不一样。

随后要按给定顺序做 $B$ 次覆写。每一次指定一个闭区间 $[P, Q]$，把其中每个格子都改成颜色 $W$。

如果从第 $U$ 格到第 $V$ 格这一段里，格子的颜色完全一致，就把 $[U, V]$ 叫做一条同色段。

每当一次覆写做完，都要汇报此刻整条带子上同色段的最大长度。

开始时，第 $k$ 格的颜色等于它自己的编号 $k$，$k$ 从 $1$ 取到 $A$。

每次覆写给出三个整数 $P$、$Q$、$W$，含义是把闭区间 $[P, Q]$ 里的颜色统一写成 $W$。

输入描述

• 第一行给出两个整数 $A$ 和 $B$。$A$ 是带子的长度，$B$ 是覆写的次数。
• 后面还有 $B$ 行。每一行三个整数 $P\ Q\ W$，按先后对应一次覆写。

数据范围：

• $1 \le A, B \le 200000$
• $1 \le P \le Q \le A$
• $1 \le W \le 1000000000$

输出描述

共写出 $B$ 行。第 $k$ 行一个整数，表示第 $k$ 次覆写完成之后，同色段的最大长度。

样例1

输入

7 4
3 5 2
6 7 2
1 1 2
4 4 8

输出

4
6
7
3

说明

开始时颜色依次是 $1,2,3,4,5,6,7$。

• 第一次把 $[3, 5]$ 改成 $2$，得到 $1,2,2,2,2,6,7$。第 $2$ 格到第 $5$ 格都是 $2$，长度 $4$。
• 第二次把 $[6, 7]$ 改成 $2$，得到 $1,2,2,2,2,2,2$。从第 $2$ 格一直到末尾都是 $2$，长度 $6$。
• 第三次把第 $1$ 格改成 $2$，七格全是 $2$，长度 $7$。
• 第四次把第 $4$ 格改成 $8$，得到 $2,2,2,8,2,2,2$。左右两段 $2$ 都是长度 $3$，答案是 $3$。

样例2

输入

4 2
2 3 6
1 4 6

输出

2
4

说明

开始时颜色是 $1,2,3,4$。

• 第一次把 $[2, 3]$ 改成 $6$，得到 $1,6,6,4$，最长为 $2$。
• 第二次把 $[1, 4]$ 改成 $6$，四格全是 $6$，最长为 $4$。