Tehtäväsi on ylläpitää vuoristomökin varauskalenteria. Saat varauksia asiakkailta ja sinun tulee käsitellä ne samassa järjestyksessä.

Jokainen asiakas ilmoittaa, moneksiko päiväksi hän haluaa varata mökin ja mikä on aikaisin mahdollinen aloituspäivä. Tehtäväsi on varata mökki asiakkaalle niin, että varaus alkaa mahdollisimman pian.

Mökissä ei ole alussa mitään varauksia. Jokainen varaus koskee peräkkäisiä päiviä, ja mökissä ei voi majoittua samaan aikaan monta asiakasta.

Syöte

Syötteen alussa on kokonaisluku n: varausten määrä.

Sen jälkeen syötteessä on n riviä, joista jokainen kuvaa yhden varauksen. Rivillä on kaksi kokonaislukua k ja a: moneksiko päiväksi varaus on ja mikä on aikaisin mahdollinen aloituspäivä.

Tuloste

Tulosta jokaiseen varaukseen päivä, jolloin asiakas saapuu mökille.

Rajat

• 1 \le n \le 10^5
• 1 \le k \le 10^6
• 1 \le a \le 10^9

Esimerkki

Syöte:

3
4 2
7 1
2 15

Tuloste:

2
6
15

Selitys: Asiakas 1 majoittuu päivät 2 \ldots 5, asiakas 2 majoittuu päivät 6 \ldots 12 ja asiakas 3 majoittuu päivät 15 \ldots 16.