Членовите на Здружението на Информатичарите на Македонија секоја недела организираат состанок, на кој се дискутираат најразлични теми поврзани со информатиката во Македонија. Во салата за состаноци на ЗИМ, секој член си има фиксно дефинирано место за седење и истиот знае точно кое место му припаѓа нему. Доколку тој не дојде на состанокот, неговото столче останува празно. Членовите седат еден до друг, во една редица, така што местото на претседателот на здружението се наоѓа најдесно на масата, местото на потпретседателот на Здружението е веднаш на лево од него, итн., наредени според линеарната хиерархија во ЗИМ.

Доколку еден член на ЗИМ земе збор, сите останати членови кои ќе ја слушнат неговата дискусија, а се погоре во хиерархијата на здружението од него (се наоѓаат десно од него), исто така земаат збор (да го пофалат за сработеното, да го искараат, итн.). Во ниту еден момент, не смее член на ЗИМ кој е подолу во хиерархијата на здружението да се вклучи во дискусијата после член кој е погоре во хиерархијата од него. На пример, доколку збор земе потпретседателот на ЗИМ, понатаму збор смее да земе само претседателот на ЗИМ (доколку е присутен) и никој друг.

За секој член на ЗИМ, вам ви е познат редниот број на столчето Xi на кое тој седи на масата за состаноци, како и неговата гласност Li. Доколку земе збор член што седи на столче Xi и е со гласност Li, него ќе го слушнат сите членови кои се наоѓаат на растојание Li од него - односно, ќе го слушнат сите членови кои се присутни и се на столчиња на позиции во интервалот од Xi-Li до Xi+Li, вклучувајќи ги и оние членови кои се наоѓаат на столчиња на самите граници на интервалот.

Ваша задача е да напишете програма која ќе пресмета, за секој член на ЗИМ, колку луѓе ќе се вклучат во дискусијата доколку тој член земе збор.

Влез

Во првата линија е запишан еден цел број N (1 <= N <= 100 000), кој го означува бројот на членови на ЗИМ кои се присутни на состанокот. Во секоја од следните N линии се наоѓаат по два цели броја Xi и Li (1 <= Xi, Li <= 1 000 000 000), кои ги означуваат редниот број на столчето и гласноста на секој од членовите - како што се тие сместени на масата, од лево на десно.

Излез

Отпечатете N цели броеви Ti, каде Ti означува колку луѓе ќе се вклучат во дискусијата доколку i-тиот член земе збор (вклучувајќи го и самиот i-ти член). Секој број треба да се отпечати во посебна линија.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
5
1 7
2 3
8 7
10 5
100 2

излез
4
1
2
1
1

Објаснување за првиот пример: Доколку првиот член земе збор, него ќе го слушнат и вториот и третиот член, кои веднаш ќе се вклучат во дискусијата (еден по друг). Кога ќе зборува третиот член, него ќе го слушне и четвртиот, кој исто така ќе се вклучи во дискусијата. Значи, доколку првиот член земе збор, вкупно ќе зборуваат 4 луѓе.

Доколку пак земе збор вториот член, него ќе го слушне само првиот, но бидејќи тој е подолу во хиерархијата на здружението, истиот нема да се вклучи во дискусијата.