002 - 温泉 (Spa)

問題

JOI 君は, クラスメイトたちと一緒に IOI 温泉に行くことにした. 温泉に行く人数は JOI 君を含めて N 人である. 幸いなことに, 今日は JOI 君たちが IOI 温泉を貸しきることに成功した.

IOI 温泉は大変人気な温泉であるため, 来たときに入浴し始める時刻を予約しておく必要がある. また, 温泉にできるだけ多くの人が入れるよう, 1 人の人が入浴できる時間は 1 時間となっている. すなわち, ある人が時刻 x に入浴を始めると, その人は時刻 x + 1 には温泉から出なければならない. また, IOI 温泉には 1 時刻に C 人までの人しか入浴ができない.

JOI 君たちは早速列になって入浴し始める時刻の予約を始めた. i (1 ≦ i ≦ N) 番目の人は時刻 Li から Ri の間のできるだけ早い時刻に入浴を始めたい. 1 番目の人が予約をする段階では, どの時刻の入浴希望人数も 0 である. ある時刻に入浴を希望している人が C 人いる場合は別の時刻に入浴を希望しないといけない. i 番目の人は, i - 1 番目までの人の予約の結果, 自分が希望しているすべての時刻で入浴できない場合, 入浴することを諦める.

JOI 君たちのために, N 人がそれぞれ入浴を始める時刻を出力するプログラムを作成せよ.

入力

入力は N + 1 行からなる.
1 行目には, N ( 1 ≦ N ≦ 300 ) と C ( 1 ≦ C ≦ 300 ) が空白区切りで与えられる.
1 + i ( 1 ≦ i ≦ N ) 行目 には, 2 つの正の整数 Li, Ri ( 1 ≦ Li ≦ Ri ≦ 100 ) が空白区切りで書かれている.

出力

i ( 1 ≦ i ≦ N ) 行目に, i 番目の人が入浴できる時刻を出力せよ. ただし, i 番目の人が入浴できない場合には -1 を出力せよ.

入出力例

入力例 1

5 2
1 1
1 2
2 3
1 4
2 2

出力例 1

1
1
2
2
-1

入力例 1 では, 5 人が IOI 温泉に行き, 1 時刻に入浴できる人数は 2 人までである. 5 番目の人以外は希望した時間に入浴できるが, 5 番目の人が指定している時刻 2 にはすでに 2 人の人が入浴しているので, 5 番目の人は入浴できない.

入力例 2

10 1
1 2
2 2
2 3
4 9
4 4
5 6
7 8
9 10
7 8
9 10

出力例 2

1
2
3
4
-1
5
7
9
8
10