Tag Discussion Solution Statistics Submit
 

RUPC 2013 (UAPC)

The Humans Braving the Invaders

Time Limit : 2 sec, Memory Limit : 65536 KB

Problem G: The Humans Braving the Invaders

Problem

現在、地球は宇宙からの侵略者であるインベーダーの攻撃を受け、人類で生き残った者は基地にいる我々だけとなった。 奴らに対抗できる戦力もほとんど残されていない。人類に勝ち目はほぼ無いと言っていいだろう。 だが、ここで我々は諦めるということはしない。 インベーダを全滅させることが、我々人類が生き残る最後の手段である。 そして、残された人類の代表として、我々は最後まで戦わなければならない。 今から最後になるであろう作戦の内容を説明する。

まず、インベーダーの戦力に比べ我々の戦力はあまりにも少ないので、この基地に立てこもり、籠城戦を行う。 この基地は高い山に囲まれていて、インベーダーが侵攻するには基地正面にある真っ直ぐな道を通る他無い。 この道をフィールドと呼ぶことにする。この特徴により、前方に集中してインベーダーを攻撃することが可能である。 基地にいる我々はインベーダーに対し2種類の武器で攻撃を行う。 1つはインベーダー1体を狙撃するスナイパーライフルである。もう1つは広範囲に攻撃ができるグレネードランチャーである。

人類でたった1人のプログラマーである君の仕事は、インベーダーと我々の行動記録を元に戦闘をシミュレーションすることだ。 行動記録はクエリー形式で与えられる。各クエリーは1つまたは複数の整数からなり、次のように与えられる。

0 インベーダーがフィールド上の、基地からの距離 L の位置に出現する。
1 d 現在フィールド上にいるすべてのインベーダーが d だけ基地に近づく。 この動作の後、基地に到達したインベーダーからダメージを受け、また、それらの敵はフィールド上から消滅する。 ダメージを受けた場合は"damage (この時基地に到達したインベーダーの数)"を1行に出力する。
2 k 現在フィールド上にいるインベーダーの数が k 体以上の場合、基地に近い方から k 番目のインベーダーをスナイパーライフルで攻撃する。 そのインベーダーはフィールド上から消滅する。そして"hit"を1行に出力する。 フィールド上のインベーダーの数が k 体未満の場合、"miss"を1行に出力する。
3 x r 基地からの距離が x の位置に範囲 r のグレネードランチャーで攻撃する。基地からの距離が x の位置に着弾し、そこからの距離が r 以下の位置にいるすべてのインベーダーはフィールド上から消滅する。 そして"bomb (倒したインベーダーの数)"を1行に出力する。補足として、基地はグレネードランチャーのダメージを受けることはない。
4 k フィールド上のインベーダーの数が k 体以上の場合、"distance (基地に近い方からk番目のインベーダーと基地との距離)"を1行に出力する。 フィールド上のインベーダーの数が k 体未満の場合、"distance -1"を1行に出力する。


作戦の説明は以上だ。総員、作戦開始!・・・幸運を祈る。

Input

入力は複数のデータセットからなる。 各データセットは以下で表される。 1行目は2つの整数 Q , L がスペース区切りで与えられる。 続く Q 行には、上記で説明したクエリーが Q 個与えられる。 入力の終わりは2つのゼロからなる。

Constraints

入力は以下の条件を満たす。

  • 入力に含まれる値はすべて整数
  • 1 ≤ Q ≤ 100000
  • 1 ≤ L ≤ 109
  • 1 ≤ d , k ≤ 109
  • 0 ≤ x L
  • 0 ≤ r ≤ 109
  • 同じ位置にインベーダーが2体以上存在することはない
  • データセットの数は3個以下

Output

各データセットにつき、出力の指示があるクエリーに対して出力せよ。各データセットの最後には"end"を出力せよ。

Sample Input

18 10
0
4 1
1 1
4 1
0
1 1
0
2 2
1 10
0
1 1
0
1 1
0
1 5
3 4 0
3 4 1
0
9 10
4 1
2 2
3 5 5
0
4 1
2 2
3 5 5
0
2 1
0 0

Sample Output

distance 10
distance 9
hit
damage 2
bomb 1
bomb 2
end
distance -1
miss
bomb 0
distance 10
miss
bomb 1
hit
end

Source: Ritsumeikan University Competitive Programming Camp 2013, Day1 , Problem set from University of Aizu teams, Shiga, Japan, 2013-03-11