pitricele

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.

Cerință

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.

Date de intrare

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\text{ xor }V_{i-1}, R_i\text{ xor }V_{i-1}, X_i\text{ 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ă.

Date de ieșire

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

Restricții și precizări

• $1 ≤ N ≤ 100 \ 000$
• $1 ≤ G_i, R_i ≤ 1 \ 000 \ 000 \ 000$
• $1 ≤ X_i ≤ i$

Exemplu

pitricele.in

3
3 4 1
6 12 5
3 5 3

pitricele.out

4
2
1

Explicație

Tripletele originale sunt:
$(3 \ 4 \ 1)$
$(2 \ 8 \ 1)$
$(1 \ 7 \ 1)$