Fișierul intrare/ieșire	hotdogs.in, hotdogs.out	Sursă	ad-hoc
Autor	Cătălin Frâncu	Adăugată de	Cătălin Frâncu • Catalin.Francu
Timp de execuție pe test	0.05 sec	Limită de memorie	8192 KB
Scorul tău	N/A	Dificultate	3.5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Hot Dogs (clasele 9-10)

Pe o stradă sunt N clădiri așezate în linie, numerotate de la 1 la N. Inițial, toate clădirile sunt nelocuite. În fiecare zi pe stradă se mută cineva: fie într-o clădire se mută oameni noi, fie unii dintre oamenii dintr-o clădire pleacă.

Un vânzător de hot dogs vine în fiecare zi la muncă, aducând cu el toneta mobilă cu hot dogs delicioși. Pentru a avea vad, el dorește să plaseze toneta cât mai aproape de centrul demografic al străzii. Mai exact, dacă p(i) este populația curentă a clădirii cu numărul i, vânzătorul vrea să plaseze toneta în dreptul unei clădiri k, cu k minim astfel încât p(1) + p(2) + ... + p(k) ≥ p(k + 1) + p(k + 2) + ... + p(n).

Vânzătorul vă roagă să-i spuneți, la sfârșitul fiecărei zile, unde să se posteze a doua zi dimineață.

Date de intrare

Fișierul de intrare hotdogs.in conține pe prima linie numerele N Z, unde N este numărul de clădiri, iar Z este numărul de zile în care vânzătorul vine pe stradă. Pe următoarele Z linii apar perechi de numere K V, cu semnificația că în/din clădirea K se mută V oameni. Când V este pozitiv, oamenii se mută în clădire, iar când V este negativ, oamenii pleacă din clădire.

Date de ieșire

În fișierul de ieșire hotdogs.out se vor scrie Z numere, câte unul pe linie. Al i-lea număr reprezintă poziția centrului demografic la sfârșitul zilei i.

Restricții

• 1 ≤ N ≤ 1.000.000
• 1 ≤ Z ≤ 100.000
• V ≠ 0
• Prin plecarea locatarilor, o clădire poate deveni nelocuită, dar (evident) nu poate avea populație negativă.
• Populația totală a străzii (suma populației clădirilor) va varia între 1 și 1.000.000.000.

Exemplu