Грег ва массив

Грегда $n$ та сондан иборат массив ва $m$ та амал бор. $i$-амал $(l_i, r_i, d_i)$: $a_{l_i}, \ldots, a_{r_i}$ элементларнинг ҳар бирига $d_i$ қўшилади.

Кейин $k$ та сўров $(x, y)$ келади: $x$-дан $y$-гача бўлган барча амалларни (рақамлари бўйича) бажариш керак. Сўровлар кетма-кет бажарилади, амал бир неча марта қўлланиши мумкин. Ҳамма сўровлардан кейинги массивни чиқаринг.

Биринчи қаторда $n$, $m$, $k$ ($1 \le n, m, k \le 10^5$). Иккинчи қаторда $n$ та бутун сон ($0 \le a_i \le 10^5$). Кейинги $m$ та қаторда $l_i$, $r_i$, $d_i$ ($1 \le l_i \le r_i \le n$, $0 \le d_i \le 10^5$). Кейинги $k$ та қаторда $x$ ва $y$ ($1 \le x \le y \le m$).

Битта қаторда $n$ та сон — якуний массив.

Икки қаватли фарқ массиви. Аввал сўровлардан ҳар бир амал неча марта бажарилишини топинг: $c_x \mathrel{+}= 1$, $c_{y+1} \mathrel{-}= 1$ ва префикс йиғинди. Кейин $i$-амал массивга $c_i \cdot d_i$ қўшади — буни ҳам фарқ массиви билан ёзинг ва охирида префикс йиғинди олинг. Ҳаммаси $O(n + m + k)$.

Қийматлар $10^{15}$ гача етади — 64 битли тур керак. Биринчи мисолда жавоб 9 18 17.

Манба: Codeforces, 295A-масала.