当前没有测试数据。

题目描述

四十大盗有一次拿到了许多金币，他们在考虑怎么分配这个财宝？思考良久，四十大盗的头领找到了阿里巴巴来一起分这个金币。现在四十大盗的团队已经发展壮大了，总共有n个大盗，从左到右一次编号为1,2,3,4,5,... ,n。

头领和阿里巴巴每次发金币都是从一个位置开始，只把金币发给这个人和他右边的所有人。但是他们发金币的规则不一样。

1、阿里巴巴发金币会从某个位置开始，依次给后面的人发1个金币。

2、头领发金币会从某个位置开始，给第一个人发1个金币，第二个人发2个金币，第三个人发3个金币...直到发给编号为n的人。

现在有m轮发金币，告诉你每轮发金币的人和开始发的位置，小朋友你能告诉我最后每个大盗分到了多少金币吗？

输入格式

第一行是两个整数n,m$(1<=n<=500000,1<=m<=400000)$。分别表示等着发金币的人数和发了几轮金币。

接下来m行，每行两个正整数 t,p$(1<=t<=2,1<=p<=n)$。 t表示发金币的规则，p表示开始发金币的位置。

输出格式

输出一行n个整数，表示每个大盗分到的金币数量。由于数据可能会很大，最终只需要输出分到的金币数$mod (10^9+7)$

输入输出样例

10 1
1 1

1 1 1 1 1 1 1 1 1 1

10 1
2 2

0 1 2 3 4 5 6 7 8 9