== include(page="template/taskheader" task_id="pitricele") ==

Poveste şi cerinţă...

 
bq. Bolovani şi pitricele, să spargă blatul cu ele.
 
Cei doi prieteni, Ţip şi Adar se joacă, folosind nişte pietre speciale, în felul următor: Ţip deţine $N$ pitricele, fiecare având câte o greutate şi o rezistenţă şi le aşează în ordine una peste alta, formând un turn vertical. Peste o pitricică având rezistenţa R se pot aşeza alte pitricele doar dacă suma greutăţilor acestora este strict mai mică decât $R$; în caz contrar, pitricica se va sparge. Dacă la un moment dat ar exista mai multe pitricele care s-ar putea sparge atunci toate se vor sparge în acelaşi timp.
Se dau $N$ triplete de forma $(G, R, X)$, cu următoarea semnificaţie: o pitricică având greutatea $G$ şi rezistenţa $R$ se adaugă în turnul deja existent, garantându-se că nu se va sparge nicio piatră din cele puse anterior. Adar trebuie să-i spună lui Ţip care este greutatea minimă pe care ar trebui să o aibă o nouă pitricică astfel încât, dacă aceasta ar fi pusă în vârful turnului, ea ar sparge cel puţin $X$ pitricele.

h2. Date de intrare

Fişierul de intrare $pitricele.in$ ...

Fişierul pitricele.in va conţine pe prima linie un număr natural $N$. Pe următoarele N linii vor fi codificate cele N triplete $(G{~i~}, R{~i~}, X{~i~})$. Astfel tripletul $(G{~i~}, R{~i~}, X{~i~})$ va fi codificat pe linia $i + 1$ ca $(G{~i~} xor V{~i~}-1, R{~i~} xor V{~i~}-1, X{~i~} xor V{~i~}-1)$ unde cu $V{~i~}$  s-a notat răspunsul lui Adar pentru Ţip după ce acesta a aşezat a $i$-a pitricică.

h2. Date de ieşire

În fişierul de ieşire $pitricele.out$ ...

Fişierul pitricele.out va avea $N$ linii, conţinând, răspunsurile lui Adar, în ordine cronologică, câte unul pe o linie.

h2. Restricţii

h2. Restricţii şi precizări

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100 000$
* $1 ≤ G{~i~}, R{~i~} ≤ 1 000 000 000$
* $1 ≤ X{~i~} ≤ i$

h2. Exemplu
table(example). |_. pitricele.in |_. pitricele.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie

| 3
3 4 1
6 12 5
3 5 3
| 4
2
1
|
 
h2. Explicaţie
 
Tripletele originale sunt:
$(3 4 1)$
$(2 8 1)$
$(1 7 1)$

...

== include(page="template/taskfooter" task_id="pitricele") ==