Laiko ribojimas: 1s

Atminties ribojimas: 1024MB

Duomenų failas: dominoes.in

Rezultatų failas: dominoes.out

Jei norite pateikti savo sprendimą - prisijunkite.

Domino

Marcelinas domisi domino dėliojimu. Bet jam atsibodo įprasti domino, todėl jis naudoja įvairaus dydžio domino detales. Marcelinas išdėlioja n domino detalių vertikaliai ant x ašies kievieną atsukęs į sekančią. Kiekvienai domino detalei Marcelinas nori sužinoti, kiek iš viso detalių nukris, jei jis pastums šią detalę į dešinę. Padėkite jam tai apskaičiuoti.

Manykime, jog domino krenta tik jei jis paliečiamas griežtai aukščiau detalės apačios.

Pradiniai duomenys

Pirmoje eilutėje pateiktas sveikasis skaičius n - domino detalių skaičius.

Sekančiose n eilučių pateikiama po du sveikuosius skaičius x_i,h_i(-10^8\\leqx_i\\leq10^8,2\\leqh_i\\leq10^8), po domino detalės koordinatę x ašyje bei detalės aukštį. Jokios dvi domino detalės nestovi toje pačioje vietoje.

Rezultatai

Atspausdinkite n tarpais atskirtų skaičių z_i - skaičių, kiek domino detalių nukris, jei Marcelinas pastums i-tąją detalę į dešinę. (įskaitant ir pastumiamą detalę).

Pavyzdžiai

Pradiniai duomenys Rezultatai 
4
16 5
20 5
10 10
18 2
 
3 1 4 1