C. Сонин массив

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Чамд $n$ бүхэл тоо $a[1], a[2], ..., a[n]$ агуулсан массив өгөгдсөн. Түүнээс гадна $m$ асуулт байгаа ба асуулт бүр $l_{i}, r_{i}, k_{i}$ гурван бүхэл тоогоор тодорхойлогдоно. Асуулт $l_{i}, r_{i}, k_{i}$ нь $l_{i} ≤ j ≤ r_{i}$ үед $a[j]$ элемент бүр дээр нэмэх хэрэгтэй гэсэн утгатай.

бичлэг нь хоёр гишүүнтийн биномиал коэффицент эсвэл $x$ элементүүдийн бүлэг дотор $y$ элементүүдийн хослолын тоо гэсэн үг.

Чи дараалан бүх асуултыг биелүүлсэний дараа эцсийн массивыг хэвлэх хэрэгтэй.

Оролт

Эхний мөр нь $n$, $m$ ($1 ≤ n, m ≤ 10^{5}$) бүхэл тоонуудыг агуулна.

Хоёр дахь мөр нь $n$ бүхэл тоонууд $a[1], a[2], ..., a[n]$ ($0 ≤ a_{i} ≤ 10^{9}$) агуулна. Энэ нь анхны массив.

Дараагийн $m$ мөрүүд нь асуулт хэлбэрээр $l_{i}, r_{i}, k_{i}$ тоонуудыг агуулна. $l_{i}... r_{i}$ хэсгийн бүх элемент дээр тоог нэмнэ ($1 ≤ l_{i} ≤ r_{i} ≤ n$; $0 ≤ k ≤ 100$).

Гаралт

$n$ бүхэл тоонууд хэвлэнэ: $i$-р тоо нь бүх асуултын дараах $a[i]$ элементийн утга юм. Утга нь хэтэрхий том тоо байж болох учраас $1000000007$ $(10^{9} + 7)$ модулиар хэвлэнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
5 1
0 0 0 0 0
1 5 0
Гаралт
1 1 1 1 1
Оролт
10 2
1 2 3 4 5 0 0 0 0 0
1 6 1
6 10 2
Гаралт
2 4 6 8 10 7 3 6 10 15
Сэтгэгдлүүдийг ачааллаж байна...