← 返回题目列表

Codeforces · 407/C

C. 奇怪的阵列

中文机器翻译题面 查看原题

你有一个由 n 个整数组成的数组:a[1]、a[2]、...、a[n]。而且,有m个查询,每个查询可以用三个整数li、ri、ki来描述。查询 li, ri, ki 意味着我们应该将 $${ \binom { j - l _ { i } + k _ { i } } { k _ { i } } }$$ 添加到每个元素 a[j],其中 li ≤ j ≤ ri。

记录 $${ \frac { y } { x } }$$ 表示二项式系数,或从 y 元素到 x 元素组的组合数。

您需要连续完成所有查询,然后打印最终数组。

输入

第一行包含整数 n, m (1 ≤ n, m ≤ 105)。

第二行包含 n 个整数 a[1], a[2], ..., a[n] (0 ≤ ai ≤ 109) — 初始数组。

接下来的 m 行包含格式为 li, ri, ki 的查询 — 向段 li...ri 的所有元素添加数字 $${ \binom { j - l _ { i } + k _ { i } } { k _ { i } } }$$ (1 ≤ li ≤ ri ≤ n; 0 ≤ k ≤ 100)。

输出

打印n个整数:第i个数是所有查询后元素a[i]的值。由于这些值可能相当大,因此以 1000000007 (109 + 7) 为模打印它们。

示例

输入 #1

5 1
0 0 0 0 0
1 5 0

输出 #1

1 1 1 1 1

输入 #2

10 2
1 2 3 4 5 0 0 0 0 0
1 6 1
6 10 2

输出 #2

2 4 6 8 10 7 3 6 10 15