题目描述

bgy 有 $n$ 个抽奖箱，编号为 $1 \sim n$，一开始每个抽奖箱都是空的

抽奖箱内可以被放入一些有编号的小球，保证所有小球除了编号以外完全相同

我们认为一个抽奖箱内，连续编号的小球越多，则幸运度越高

连续编号是指一些小球的编号能组成差值为 $1$ 的等差数列

一个抽奖箱的幸运度定义为: 这个抽奖箱内最长的连续编号小球数量

例如一个抽奖箱内存在以下五个小球: $2,4,5,6,8$，那么这个抽奖箱的幸运度即为 $3$

现在 bgy 每次可以在编号区间为 $[l, r]$ 的抽奖箱内同时加入编号为 $x$ 的小球

现在 bgy 想知道，当他进行完所有操作以后，每个抽奖箱的幸运度是多少？

输入格式

第一行包含两个整数 $n,m$，表示有 $n$ 个抽奖箱有 $m$ 次操作

接下来 $m$ 行每行包含三个数字 $l,r,x$，表示 bgy 这次操作会在编号为 $[l,r]$ 的每个抽奖箱内都加入编号为 $x$ 的小球

输出格式

只有一行包含 $n$ 个整数，分别表示每个抽奖箱的幸运度

数据范围

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

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

对于 $100\%$ 的数据, $n,m \leq 100000,1 \leq x \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