You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

很久很久以前，有位国王和王后，他们因为没有孩子而整天忧愁。有一天，王后正在洗澡的时 候冒出一只小龙虾，告诉王后说「你将会生下一位公主」。 王后果然生了个一位美丽的公主。 国王决定举行一场盛大的宴会。可是国王只有十二只金盘子，没有办法邀请完王国里全部的魔 女。 在宴会上，魔女们纷纷为公主送去了美好的礼物。 第一位赠送美好的心灵，第二位赠送美丽的容貌——但就在第十一位魔女向公主送完礼物的时 候，没有被邀请的第十三位魔女出现了。 她高声释放出可怕的诅咒 「公主在十五岁时，将被一台纺车的针刺死」 国王和王后大惊失色。 可是，第十二个还没有献上美好祝愿的魔女说 「公主不会死去，但会沉睡，而且会睡上一百年」 国王为了就心爱的公主，下令将王国里的所有纺车全部烧掉了。 随着时间的流逝，公主迎来了她十五岁的生日，但恰恰那一天，国王和王后都不在家。 公主觉得无聊，在城堡里到处乱逛，来到了一个古老的城楼。 她登上楼顶，看到屋里有一个老婆婆正坐在纺车前面纺纱，自己也想试试，便去碰纺车。就在 这时，纺车的针就扎进了公主的手指。 就像诅咒说的一样，公主陷入了沉睡。 正好国王和王后带着部下回到了城堡。 此时公主已经陷入无比漫长的沉睡中。回到城堡的他们也都纷纷闭上了眼睛。城堡里的所有人 ——厨师、女佣、马、鸽子、狗、就连苍蝇还有火焰全都睡着了。 城堡的四周长出了荆棘，转眼间长得很高很高。 最后，整座城堡完全围在了里面沉睡了一百年。 有不少王子听到美丽公主的传说来探险，尝试冲进蒺藜树丛。 但是，从来没有人成功。

「我就是诅咒故事里公主的那个第十三位魔女」 「故事已经过去了一百年，但城堡依然被封锁着」 「咦，在原本的故事里，应该是『一百年后，王子来到城堡，荆棘自动为他敞开道路』」 「是的，应该是那样才对。可是，荆棘依旧紧紧相互缠绕在一起，我实在无计可施」 萨拉四下望了望，荆棘的确像岩石一样紧紧地纠缠着。 仔细一看，里面还混有人的遗骨。魔女咬紧嘴唇，向萨拉低下头 「请你们把公主叫醒」

萨拉想要唤醒公主就必须穿越荆棘，荆棘可以视为围绕城堡的许多同心圆，每个圆就是一圈荆棘。 我们可以从外向内给每一圈荆棘编号，第 $i$ 圈荆棘的高度为 $h_i$。

最开始时，荆棘并不存在，即所有的 $h_i=0$。之后，魔女开始施展魔法。 魔女施展的每一次魔法都可以用两个正整数 $a,b$ 来表示，含义如下

• 在第 $1$ 到 $a$ 圈荆棘中选出高度最小的一个，如果存在多个则选最靠外，然后将这一圈荆棘的高度加一
• 重复上述操作 $b$ 次

魔女把她施展的 $m$ 次魔法以及每次魔法的参数 $a_i,b_i$ 都告诉了萨拉。 萨拉想知道最终会形成什么样子荆棘，但她没学过编程，所以只能求助于你啦。

输入格式

第一行包含两个整数 $n,m$，表示荆棘的圈数和魔女施展魔法的次数。 第二行到第 $m+1$ 行，每行两个整数，第 $i+1$ 行包含 $a_i,b_i$ 两个整数，为第 $i$ 道魔法的参数。

输出格式

输出 $n$ 行，每行一个整数，依次为从外到内的荆棘的高度，即 $h_1,h_2,\dots,h_n$。

样例

输入1

9 3
5 11
8 4
4 7

输出1

4
4
4
4
2
2
1
1
0

输入2

6 6
3 5
6 11
1 6
4 7
5 2
2 5

输出2

10
10
5
5
4
2

数据范围与提示

对于全部数据，满足 $1\le n,m\le 10^5,1\le a_i\le n,1\le b_i \le 10^9$。