Problem 4165: Cadouri

Ioana e o mamica tanara care are doi copii de varste apropiate. Ca in orice familie, cei doi frati se invidiaza intre ei. Pe Ioana o deranjeaza foarte tare acest aspect si le promite copiilor cate un cadou pe zi aceluia care a fost cel cuminte dintre ei in ziua respectiva. In general, intr-o zi copiii fac si fapte bune si fapte rele, este foarte greu sa fie puse in balanta faptele lor, asa ca tot Ioana este cea care decide care e cel care va primi cadoul. Mai exista un aspect: dupa ce a primit un cadou, fratele respectiv se straduieste pe mai departe sa fie si mai cuminte, cum e si normal; prin urmare fiecare din cei doi copii vor primi cadourile mai multe zile la rand, pana cand sa-i vina randul si celuilalt frate sa-si primeasca cadoul.
Ioana s-a plimbat prim magazine si si-a facut planul cam cat va cheltui cu cadourile in fiecare zi. Ea isi iubeste cei doi copii la fel de mult si nu doreste ca vreunul dintre ei sa fie dezavantajat, asa ca incearca sa faca in asa fel incat diferenta dintre sumele cadourilor pe care le primesc cei doi copii sa fie minima.
Ioana mai are o sora, Andreea. Andreea nu are copii, prin urmare isi doreste foarte mult sa se apropie de copiii Ioanei. Andreea vine si ea cu cadouri pentru copii. Andreea lucreaza in salturi: cand e foarte aglomerata mai multe zile la rand, cand e libera mai multe zile la rand. Atunci cand e aglomerata la serviciu, Andreea nu poate veni sa-si viziteze nepotii, dar cand are perioadele mai lejere vine la ei in fiecare zi. Andreea stie cam ce-si doresc copiii, nu prea ii place sa umble prin magazine sa caute si nici nu vrea s-o supere pe Ioana, asa ca atunci cand isi viziteaza nepotii, ea vine cu o suma de bani pentru cadou pe care o da Ioanei si o lasa pe Ioana sa hotarasca ce cadou cumpara.

Cerință

Cerinta 1
Sa se afiseze valorile $a[0]$ , $a[1]$ , … $a[n-1]$ ale cadourilor copiilor, dupa interventiile Andreei.
Cerinta 2
Sa se determine indicele $p (0 \leq p \le n - 1)$ cu proprietatea că sumele alocate cadourilor $a[0]$ + $a[1]$ +...+ $a[p]$ și $a[p+1]$ +...+ $a[n-1]$ sa fie cât mai apropiate, adica diferența în modul a acestor sume sa fie minimă. Dacă există mai multe astfel de poziții $p$ , se va alege cea mai din stânga.

Date de intrare

Pe prima linie a fișierului de intrare cadouri.in se afla $n$ , numarul de zile in care cei doi copii vor primi cadouri.
Pe a doua linie a fisierului se afla $n$ valori intregi, sumele de bani $a[0]$ , $a[1]$ , … $a[n-1]$ pe care si le-a rezervat Ioana pentru cadourile copiilor, pentru fiecare zi.
Pe linia a treia a fisierului se gaseste o valoare intreaga $c$ care poate avea doar valoarea 1 sau valoarea 2, numarul cerintei pe care o rezolvati.
Pentru cerinta 1 pe linia a patra se afla $m$ , numarul de perioade in care Andreea nu este aglomerata, iar pe urmatoarele $m$ linii se vor gasi cele $m$ “interventii” ale Andreei; fiecare interventie este formata din trei numere $st$ , $dr$ si $x$ cu semnificația ca in fiecare zi cu indicele cuprins între $st$ și $dr$ Andreea aduce o suma de bani de valoare $x$ .
Pentru cerinta a doua nu mai sunt alte valori de citit.

Date de ieșire

Pentru cerinta $1$ , pe prima linie a fișierului de ieșire cadouri.out se vor găsi cele $n$ valori întregi, $a[0]$ , $a[1]$ , … $a[n-1]$ care reprezinta sumele de bani alocate cadourilor pentru fiecare zi, dupa toate interventiile Andreei.

Restricții și precizări

$1 \leq n,m,x \leq 200 \ 000$
$1 \leq st,dr \leq n$
$C \in \left\{ 1,2 \right\}$

Exemplul 1

cadouri.in

10 
1 1 2 4 6 3 5 9 7 3 
1
6
8 10 2
3 10 3
5 9 7
5 5 5
6 7 2
1 1 1

cadouri.out

1 2 2 7 9 18 17 21 19 15

Exemplul 2