题目描述

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

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

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

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

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

输入格式

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

接下来$m$行，每行两个正整数 $t,p$ $(1 \le t \le 2,1 \le p \le 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

对于 30% 的数据 ， $n \le 1000 , m \le 2000$;