Problema Depozit

Tatăl lui Andrei are un depozit de marfă. Deoarece urmează o perioadă aglomerată Andrei și-a propus să-și ajute tatăl pentru a avea gestiunea corectă a obiectelor din depozit. În depozit se află N obiecte numerotate de la 1 la N, iar fiecare obiect are un stoc. Pe parcursul unei perioade de timp, la depozit au loc T operații. O operație este fie de intrare (când obiectul intră în depozit), fie de ieșire (când obiectul iese din depozit), astfel:

1. x y p: stocul obiectelor cu indici cuprinși între [x, y] creste cu p
2. x y p: stocul obiectelor cu indici cuprinși între [x, y] scade cu p

În urma unei operații de tip 2 se poate ca stocul sa fie negativ, caz în care proprietarul rămâne cu datorie.

Cerință

Dându-se numărele naturale N și T, precum și T întrebări definite ca mai sus, să se răspundă la cele T întrebări.

Date de intrare

Programul citește din fișierul depozit.in numărul N, pe urmatoarea linie N numere naturale reprezentând stocul depozitului, pe a treia linie T, și apoi T întrebări definite ca mai sus.

Date de ieșire

Programul va afișa în fișierul depozit.out stocul pentru fiecare obiect dupa cele T operatii.

Restricții și precizări

• 1 ≤ N ≤ 100.000
• 1 ≤ T ≤ 100.000
• 0 ≤ stoc[i] ≤ 100.000
• 0 ≤ p ≤ 100.000

Exemplu