Jackは彼の住む家をとても気に入っていた. 彼の家の塀の上で毎日のように愛くるしいねこたちが昼寝をしているからだ. Jackはねこがとても好きだった.
Jackは, 夏休みの自由研究としてねこたちの観察日記を付けることにした. しばらく観察しているうちに, 彼はねこたちの面白い特徴に気付いた.
塀は W[尺] の幅があり, ここにねこたちは並んで昼寝をする. それぞれのねこたちは体の大きさが違うので, 昼寝に必要とする幅もまた異なる. 昼寝をしにきたねこは, 自分が寝られる場所があれば, そこで昼寝をする. ただし, そのような場所が複数ある場合はより左側で昼寝をし, 十分な幅が無ければ諦めて帰ってしまう. しばらく昼寝をしたねこは、起きると塀から飛び降りてどこかへと行ってしまう.
Jackはねこたちを観察して, その行動をノートに書き留めた. しかし, とても多くのねこが昼寝をしていたので, この記録を集計するのはとても大変である. プログラムを書いて, ねこたちが昼寝をした場所を求めるのを手伝ってほしい.
入力ファイルは, 複数のデータセットを含む. それぞれのデータセットの最初の行は2つの整数を含み, それぞれ塀の幅 W と, 後に続く行数 Q を表す.
以下のQ行に, ねこの観察記録が与えられる. 各行は, 以下のいずれかの書式に従う.
s [id] [w]
w [id]
前者は, ねこの sleep 記録であり, ねこが昼寝をしに来たことを表す. id はねこの名前を表す整数であり, w はそのねこが昼寝に必要とする幅 [尺]である.
後者は, ねこの wakeup 記録であり, 名前がidであるねこが起きたことを表す.
この記録は, 時系列順に与えられる.
どのねこも2回以上昼寝をすることはない. また, Jackの記録に矛盾は無いものとする. つまり, あるねこの sleep 記録に対して, そのねこが昼寝することが出来た場合, またその場合に限って, そのねこの wakeup 記録が(より後の行に)与えられる.
W, Q ≤ 100 と仮定してよい.
W と Q がともに 0 のとき、入力の終わりを示す. このデータセットに対する出力を行ってはならない.
入力のsleep記録が与えられるたびに, 1行出力せよ. この行は, もしそのねこが昼寝できた場合, その位置を表す数字を含まなければならない. ねこが塀の左端を起点として b [尺] から b+w [尺] の場所で昼寝したならば, b を出力せよ. そのねこが昼寝できなかった場合, "impossible" と出力せよ.
データセットの終わりに, "END"と出力せよ.
4 6 s 0 2 s 1 3 s 2 1 w 0 s 3 3 s 4 2 3 3 s 0 1 s 1 1 s 2 1 0 0
0 impossible 2 impossible 0 END 0 1 2 END