Greg va massiv

Gregda $n$ ta sondan iborat massiv va $m$ ta amal bor. $i$-amal $(l_i, r_i, d_i)$: $a_{l_i}, \ldots, a_{r_i}$ elementlarning har biriga $d_i$ qo'shiladi.

Keyin $k$ ta so'rov $(x, y)$ keladi: $x$-dan $y$-gacha bo'lgan barcha amallarni (raqamlari bo'yicha) bajarish kerak. So'rovlar ketma-ket bajariladi, amal bir necha marta qo'llanishi mumkin. Hamma so'rovlardan keyingi massivni chiqaring.

Birinchi qatorda $n$, $m$, $k$ ($1 \le n, m, k \le 10^5$). Ikkinchi qatorda $n$ ta butun son ($0 \le a_i \le 10^5$). Keyingi $m$ ta qatorda $l_i$, $r_i$, $d_i$ ($1 \le l_i \le r_i \le n$, $0 \le d_i \le 10^5$). Keyingi $k$ ta qatorda $x$ va $y$ ($1 \le x \le y \le m$).

Bitta qatorda $n$ ta son — yakuniy massiv.

Ikki qavatli farq massivi. Avval so'rovlardan har bir amal necha marta bajarilishini toping: $c_x \mathrel{+}= 1$, $c_{y+1} \mathrel{-}= 1$ va prefiks yig'indi. Keyin $i$-amal massivga $c_i \cdot d_i$ qo'shadi — buni ham farq massivi bilan yozing va oxirida prefiks yig'indi oling. Hammasi $O(n + m + k)$.

Qiymatlar $10^{15}$ gacha yetadi — 64 bitli tur kerak. Birinchi misolda javob 9 18 17.

Manba: Codeforces, 295A-masala.