题目描述

在今天的竞赛课上，老师给全班同学出了一道难题给出一个长度为 n 数组 A$_1$,A$_2$, ... ,A$_n$，初始值都为 0。

我现在给出 m 个操作，请你输出操作后的序列。

操作共有两种：

1 l r:将下标在区间 [l,r] 的元素的值都加 1。 这时，zqh_wz便嚷嚷道:“这不是大水题吗?老师笑了:"“别急别急，还有一个操作呢’

2 l r:将操作编号在区间 [l,r] 的操作再执行一次。

输入格式

第一行两个正整数n,m，表示数组长度与操作数量。

接下来m行，每行三个整数 op l r ，表示一个操作，格式如题目描述所示。

操作编号从1开始。

对于操作1，保证1<=l<=r<=n；对于操作2，保证1<=l<=r<id，id为当前操作的编号。

输出格式

输出仅一行，n个用空格隔开的数，表示操作后的数组。

由于数字可能很大，请输出对10$^9$+7取模后的结果。

样例

输入1

1 2
1 1 1
1 1 1

输出1

2

输入2

5 5
1 1 2
1 4 5
2 1 2
2 1 3
2 3 4

输出2

7 7 0 7 7

数据范围与提示

对于20%的数据，n,m<=10

对于60%的数据，n,m<=2000

对于100%的数据，1<=n,m<=10$^5$