Пратениците во една држава добиваат огромни средства за патни трошоци, што предизвикува голем гнев кај народот. Исто така, знаеме дека пратениците во парламентот се организирани хиерархиски, па за секој пратеник знаеме кој (пратеник) му е претпоставен нему (ова се прави со цел полесно да се организира донесувањето на закони и слично). Само претседателот на парламентот нема свој претпоставен.

Една од идеите за надминување на проблемот со патните трошоци е пратениците да добиваат исплата на трошоците во биткоини, наместо во денари. Сепак, за да се убедат пратениците да гласаат за овој предлог, мора да биде задоволена нивната посакувана исплата (колку биткоини месечно тие би сакале да добиваат за патни трошоци). Не е дозволено некој претпоставен да зема помала вредност од некој негов подреден, па доколку некој пратеник побара таква исплата, тогаш автоматски се зголемува (изедначува) исплатата и на неговиот претпоставен, па доколку ова предизвика проблем со неговиот претпоставен, се менува и неговата исплата, итн., рекурзивно.

На влез, даден ви е бројот на пратеници N (не вклучувајќи го претседателот), и вредност B која означува колку биткоини сака да добива месечно претседателот на собранието. Понатаму, за секој друг пратеник (во редослед по кој истите ќе бидат контактирани за нивното мислење), ќе ви биде дадена нивната посакувана исплата (во биткоини/месечно), како и информација за тоа кој е нивниот претпоставен во собранието. За секој од овие N пратеници, отпечатете на колку претпоставени ќе им се зголеми исплатата поради тоа што пратеникот побарал поголема вредност. Претпоставените секогаш ќе бидат контактирани (за нивната вредност) пред нивните подредени пратеници.

Влез

Во првиот ред се запишани два цели броја N (1 <= N <= 300000) и B (1 <= B <= 1000000000). Во секој од следните N редови се запишани по два цели броја Ri (1 <= Ri <= 1000000000) и Pi (0 <= Pi < N), каде Ri е бараната исплата на i-тиот пратеник, а Pi е ознаката на неговиот претпоставен (претседателот на собранието има ознака 0, првиот пратеник даден во влезните податоци има ознака 1, вториот има ознака 2, итн).

Забелешка: Во тест случаи кои носат најмалку 40% од поените, N ќе биде цел број помал или еднаков на 10000.

Излез

Отпечатете N броја (во посебна линија), како што се бара во задачата.

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

Временско ограничување: 2 seconds
Мемориско ограничување: 256 megabytes

Примери

влез
5 400
350 0
300 1
450 2
420 0
550 3

излез
0
0
3
0
4

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