004 - 鍵山食堂

問題

雛ちゃんだ。_{かわいいね}

雛ちゃんの最近の流行は給食ごっこである。_謎だね

何個かの人形を用意し、「待機列」に一列に並べる。_利口だね

並べられた人形は、先頭から順に「食堂」と呼ばれる檻に順番に入れていく。_檻だって

「食堂」には収容限界があり、一定数の人形しか入れることが出来ない。_{それはそうだね}

給食ごっこ開始時、同時刻に収容限界数と同じ数だけの人形が「食堂」に入る。

各人形には「食事時間」が設定されており、

この時間が経過すると人形は「食堂」から外に出て、

「待機列」先頭の人形が「食堂」に入る。

例によって、給食ごっこを行うプログラムを作成してください。_{よろしくね}

入出力形式

入力形式

一行目に、人形の数 n , 食堂の収容限界数 m が空白区切りで与えられる。

次からN行に渡り、待機列に並んでいる人形の番号 id ,

人形の食事時間 t が空白区切りで与えられる。

n m
id1 t1
id2 t2
..
..
idn tn

出力形式

食堂から出てくる人形の番号を、出てきた順に改行込みで出力せよ。

同じ時間に人形が出てくる場合は、番号が小さい順に出力すること。

制約

• 1 ≦ m ≦ n ≦ 1000000
• 1 ≦ id ≦ n
• id_i ≠ id_j(i≠j)
• 1 ≦ t ≦ 1000

部分点

(1 ≦ m ≦ n ≦ 1000)を満たすテストケースに正解すると、配点の20%が与えられる。

入出力例

入力例

6 3
1 5
2 15
6 2
5 11
3 10
4 8

出力例

6
1
5
2
3
4