小w和他的两位队友teito、tokitsukaze准备为大家发点福利，到底发点什么呢？思考良久之后他们三个人准备了很多很多的糖果。他们让n个小朋友们排成一长排并且从左到右依次标号为$1,2,3,4,5,6,7,8,9 ... n$。 三人每次发糖果，都是从某一个位置开始，只把糖果发给这个人以及这个人右侧的所有人。但是他们发糖果的规则有所不同。 1、如果某轮发糖果的是tokitsukaze，她将会从一个位置$pos$开始，依次向右给每个人$1$个糖果。 2、如果某轮发糖果的是teito，他将会从一个位置$pos$开始，依次向右，他将会给他碰到的第一个人发$1$个糖果，给他碰到的第二个人发$2$个糖果，给他碰到的第三个人发$3$个糖果 $...$ 碰到的第$k$个人发$k$个糖果，直到向右走到编号为$n$的人为止。 3、如果某轮发糖果的是winterzz1，众所周知小w是个大方的人，所以他发的糖最多，他将会从一个位置$pos$开始，依次向右，它将会给他碰到的第一个人发$1$个糖果，给他碰到的第二个人发$4$个糖果，给他碰到的第三个人发$9$个糖果$...$ 碰到的第k个人发$𝑘^2$个糖果直到向右走到编号为n的人为止。 发糖的福利一共进行了$m$轮，现在告诉你这$m$轮发糖的人和他们该轮发糖的起始位置$pos$，请你告诉我这$m$轮发糖结束后$1$到$n$每个人手中糖果的数量，为了避免这个数字过大，你只用输出每一个人手中糖的数量$𝑚𝑜𝑑10^9+7$后的结果即可。

第一行一个正整数T（$1 \le T \le 10$），表示有T组测试案例。对于每组案例： 第一行是两个正整数n,m($1 \le n,m \le 1e5$)表示现在有一排n个人并且进行了m轮发糖果。 接下来m行，每行两个正整数type($1\le type \le 3$),pos($1 \le pos \le n$)分别表示该轮发糖果的人，以及这个人开始发糖果的位置。 type=1时发糖果的人为tokitsukaze，type=2时发糖果的人为teito，type=3时发糖果的人为winterzz1。pos表示位置，并且最左边的人pos为1，最右边的人pos为n。

对于每组测试案例，输出一行n个非负整数，表示每个人手中的糖果数量$mod 10^9+7$后的结果。数字与数字之间用空格隔开。

由于输入量和输出量比较大, 使用cin,cout进行输入输出请关闭同步流。