题目描述

有 $n$ 个存储单元，每个单元可以存储一个整数，这些单元的编号为 $1$ 到 $n$ 。一开始，每个单元的数字都是 $0$，接下来依次有 $m$ 条指令：

• 第一种指令以 + 开头，后接两个整数 $l$ 与 $r$，含义是将编号 $l$ 到编号 $r$ 单元的数字分别加一。
• 第二种指令以 * 开头，后接两个整数 $l$ 与 $r$，含义是重复执行第 $l$ 条指令到第 $r$ 条指令。保证这些指令的序号都在当前指令之前。

请输出每个单元格最后的数字，由于可能很大，输出它们模 $1,000,000,007$ 的余数。

输入格式

第一行：两个整数 $n$ 与 $m$ 第二行到第 $m+1$ 行：在第 $i+1$ 行，先有一个字符 + 或 *，后接两个整数 $l$ 与 $r$

• 若是 +，则保证 $1\leq l\leq r\leq n$
• 若是 *，则保证 $1\leq l\leq r<i$

输出格式

共 $n$ 行，第 $i$ 行只有一个数表示第 $i$ 个单元内存储的整数模 $1,000,000,007$ 的余数

3 3
+ 2 3
+ 1 2
* 1 2

2 
4 
2

数据范围

• 对于 $30\%$ 的数据，$1\leq n,m\leq 20$
• 对于 $60\%$ 的数据，$1\leq n,m\leq 1000$
• 对于 $100\%$ 的数据，$1\leq n,m\leq 200,000$