暂无测试数据。

你喜欢连续段吗?

你喜欢集合吗?

Star-dust:我不喜欢。

illyasviel:那也没办法，这题你还是得做的。

Star-dust:QWQ。

有 $n$ 个集合，$m$ 次操作，每次输入 $l,r,x$ 表示往 $l$ 到 $r$ 都插入 $x$ 。

最后对每个集合都询问他的最长连续段的长度是多少。

连续段 $[l,r]$ 定义为在集合 $S$ 中 $l$ 到 $r$ 的元素都出现过。

输入格式

第一行两个数 $n,m$ 表示集合的个数和操作次数。

接下来 $m$ 行每行三个数 $l,r,x$ 表示往集合 $l$ 到集合 $r$ 都插入 $x$ 。

输出格式

输出一行 $n$ 个数，第 $i$ 个数代表集合 $i$ 的最长连续段。

数据范围与约定

对于 $30\%$ 的数据, $n,m \leq 1000$

对于 $30\%$ 的数据, $l,r$ 随机。

对于 $100\%$ 的数据, $n,m \leq 100000,1 \leq a \leq 10^9$

除 $100\%$ 的数据其他数据没有交集，保证同一个元素不会被多次插入同一个集合。

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

5 5 6 5 1 1 1 1 1 1