题目描述

有 $n$ 个存储单元，一开始，所有单元都是 $0$，接下来依次进行 $q$ 条修改操作：

• 加法修改操作以字符 + 开头，后接两个整数 $p$ 与 $d$，表示第 $p$ 个单元将增加 $d$；
• 乘法修改操作以字符 * 开头，后接一个整数 $m$，表示所有单元都将变成原数字的 $m$ 倍。

请输出每个单元最后的数值。由于答案可能很大，输出这些数各自模 $1,000,000,007$ 的余数。

输入格式

• 第一行：两个整数表示 $n$ 与 $q$。
• 第二行到第 $q+1$ 行：第 $i+1$ 行首先有一个字符表示操作类型
  • 若是加法修改，后接两个整数 $p_i$ 与 $d_i$
  • 若是乘法修改，后接一个整数 $m_i$

输出格式

• 单独一行：$n$ 个数字，表示各单元模 $1,000,000,007$ 的余数。

3 5
+ 1 3
* 10
+ 2 6
+ 3 9
* 5

150 30 45

数据范围

• 对于 $40\%$ 的数据，$n,q\leq 1000$
• 对于 $80\%$ 的数据，$n,q\leq 50000$
• 对于 $100\%$ 的数据，$n,q\leq 200,000$
• $1\leq d_i,m_i\leq 1,000,000$