K. 说重话！！！
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

小 A 迷上了一款三字游戏，天天摸鱼并在三字游戏里战斗爽！！！他的 mentor 知道后十分生气，对小 A 说了重话，在小 A 没拿出接下来 $$$n$$$ 天的具体奋斗方案之前，实行一刀切的禁娱计划，不接受任何争议！！！

小 A 的好好师兄牛哥在去上班前给小 A 拟定了一份 $$$m$$$ 项的奋斗清单。清单每行包含两个数字，分别代表奋斗事项类型和从第几天开始。已知对于第 $$$x$$$ 天开始的奋斗事项有：

  • 奋斗事项 1：从 $$$x$$$ 天开始多奋斗 $$$1$$$ 小时，第 $$$x+1$$$ 天多奋斗 $$$2$$$ 小时，第 $$$x+2$$$ 天多奋斗 $$$3$$$ 小时... ，从 $$$x$$$ 天往后的第 $$$k$$$ 天多奋斗 $$$k+1$$$ 个小时，持续到第 $$$n$$$ 天。

  • 奋斗事项 2：从 $$$x$$$ 天开始多奋斗 $$$1$$$ 小时，第 $$$x+1$$$ 天多奋斗 $$$4$$$ 小时，第 $$$x+2$$$ 天多奋斗 $$$9$$$ 小时... ，从 $$$x$$$ 天往后的第 $$$k$$$ 天多奋斗 $$$(k+1)^2$$$ 个小时，持续到第 $$$n$$$ 天。

现请你编写一份程序帮小 A 制定具体的奋斗方案，帮他算出每天需要奋斗多少个小时。由于这个数字可能较大，请输出答案对 $$$10^9+7$$$ 取模后的结果。

Input

第一行一个正整数 $$$T$$$ ($$$1\le T\le 10^4$$$) 表示测试用例数。

对于每组测试用例：

  • 第一行包含一个 $$$n$$$ ($$$1\le n\le 10^5$$$) 和 $$$m$$$ ($$$1\le m\le 10^5$$$)，表示接下来奋斗的天数和牛哥的清单有多少项。

  • 接下来 $$$m$$$ 行，每行包含两个数字 $$$op$$$ ($$$1\le op\le 2$$$) 和 $$$x$$$ ($$$1\le x\le n$$$)，分别表示奋斗事项类型和从第几天开始。

保证所有测试用例的 $$$n$$$ 之和与 $$$m$$$ 之和均不大于 $$$10^5$$$

Output

对于每组测试用例，输出一行 $$$n$$$ 个整数，其中第 $$$i$$$ 个数表示第 $$$i$$$ 天需要奋斗小时数对 $$$10^9+7$$$ 取模后的结果。

Example
Input
2
6 4
1 3
2 1
2 5
1 1
10 2
2 2
2 7
Output
2 6 13 22 34 50
0 1 4 9 16 25 37 53 73 97
Note

我们姑且认为小 A 所在的世界一天有不止 24 个小时。