Problem:


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



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

Submission status: Wrong Answer

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1515

for i in range(3):
	firstInput = input()
	if firstInput == "0 0":
		break
	else:
		invader = []
		Q = int(firstInput.split(" ")[0])
		L = int(firstInput.split(" ")[1])
		for j in range(Q):
			otherInput = input()
			inputList = []
			for k in range(len(otherInput.split(" "))):
				inputList.append(int(otherInput.split(" ")[k]))
			if inputList[0] == 0:
				invader.append(L)
			elif inputList[0] == 1:
				for l in range(len(invader)):
					invader[l] -= inputList[1]
				a = 0
				b = []
				for l in range(len(invader)):
					if invader[l] <= 0:
						a += 1
				for l in range(a):
					del invader[0]
				if a > 0:
					print("damage " + str(a))
			elif inputList[0] == 2:
				if len(invader) < inputList[1]:
					print("miss")
				else:
					del invader[inputList[1]-1]
					print("hit")
			elif inputList[0] == 3:
				a = 0
				b = []
				for l in range(len(invader)):
					if invader[l] > inputList[1]:
						if invader[l] - inputList[1] <= inputList[2]:
							a += 1
							b.append(l)
					else:
						if inputList[1] - invader[l] <= inputList[2]:
							a += 1
							b.append(l)
				print(b)
				for l in range(len(b)):
					del invader[b[0]]
				print("bomb " + str(a))
			elif inputList[0] == 4:
				if len(invader) < inputList[1]:
					print("distance -1")
				else:
					print("distance "+str(invader[inputList[1]-1]))
			print(invader)
		print("end")

Submission status: Wrong Answer

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1515

for i in range(3):
	firstInput = input()
	if firstInput == "0 0":
		break
	else:
		invader = []
		Q = int(firstInput.split(" ")[0])
		L = int(firstInput.split(" ")[1])
		for j in range(Q):
			otherInput = input()
			inputList = []
			for k in range(len(otherInput.split(" "))):
				inputList.append(int(otherInput.split(" ")[k]))
			if inputList[0] == 0:
				invader.append(L)
			elif inputList[0] == 1:
				for l in range(len(invader)):
					invader[l] -= inputList[1]
				a = 0
				b = []
				for l in range(len(invader)):
					if invader[l] <= 0:
						a += 1
				for l in range(a):
					del invader[0]
				if a > 0:
					print("damage " + str(a))
			elif inputList[0] == 2:
				if len(invader) < inputList[1]:
					print("miss")
				else:
					del invader[inputList[1]-1]
					print("hit")
			elif inputList[0] == 3:
				a = 0
				b = []
				for l in range(len(invader)):
					if invader[l] > inputList[1]:
						if invader[l] - inputList[1] <= inputList[2]:
							a += 1
							b.append(l)
					else:
						if inputList[1] - invader[l] <= inputList[2]:
							a += 1
							b.append(l)
				print(b)
				for l in range(len(b)):
					del invader[b[0]]
				print("bomb " + str(a))
			elif inputList[0] == 4:
				if len(invader) < inputList[1]:
					print("distance -1")
				else:
					print("distance "+str(invader[inputList[1]-1]))
			#print(invader)
		print("end")

Submission status: Time Limit Exceeded

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1515

for i in range(3):
	firstInput = input()
	if firstInput == "0 0":
		break
	else:
		invader = []
		Q = int(firstInput.split(" ")[0])
		L = int(firstInput.split(" ")[1])
		for j in range(Q):
			otherInput = input()
			inputList = []
			for k in range(len(otherInput.split(" "))):
				inputList.append(int(otherInput.split(" ")[k]))
			if inputList[0] == 0:
				invader.append(L)
			elif inputList[0] == 1:
				for l in range(len(invader)):
					invader[l] -= inputList[1]
				a = 0
				b = []
				for l in range(len(invader)):
					if invader[l] <= 0:
						a += 1
				for l in range(a):
					del invader[0]
				if a > 0:
					print("damage " + str(a))
			elif inputList[0] == 2:
				if len(invader) < inputList[1]:
					print("miss")
				else:
					del invader[inputList[1]-1]
					print("hit")
			elif inputList[0] == 3:
				a = 0
				b = []
				for l in range(len(invader)):
					if invader[l] > inputList[1]:
						if invader[l] - inputList[1] <= inputList[2]:
							a += 1
							b.append(l)
					else:
						if inputList[1] - invader[l] <= inputList[2]:
							a += 1
							b.append(l)
				#print(b)
				for l in range(len(b)):
					del invader[b[0]]
				print("bomb " + str(a))
			elif inputList[0] == 4:
				if len(invader) < inputList[1]:
					print("distance -1")
				else:
					print("distance "+str(invader[inputList[1]-1]))
			#print(invader)
		print("end")

Submission status: Time Limit Exceeded

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1515

for i in range(3):
	firstInput = input()
	if firstInput == "0 0":
		break
	else:
		invader = []
		Q = int(firstInput.split(" ")[0])
		L = int(firstInput.split(" ")[1])
		for j in range(Q):
			otherInput = input()
			inputList = []
			for k in range(len(otherInput.split(" "))):
				inputList.append(int(otherInput.split(" ")[k]))

			if inputList[0] == 0:
				invader.append(L)

			elif inputList[0] == 1:
				for l in range(len(invader)):
					invader[l] -= inputList[1]
				a = 0
				b = []
				for l in range(len(invader)):
					if invader[l] <= 0:
						a += 1
				if a > 0:
					for l in range(a):
						del invader[0]
					print("damage " + str(a))

			elif inputList[0] == 2:
				if len(invader) < inputList[1]:
					print("miss")
				else:
					del invader[inputList[1]-1]
					print("hit")

			elif inputList[0] == 3:
				a = 0
				b = []
				for l in range(len(invader)):
					if invader[l] > inputList[1]:
						if invader[l] - inputList[1] <= inputList[2]:
							a += 1
							b.append(l)
					else:
						if inputList[1] - invader[l] <= inputList[2]:
							a += 1
							b.append(l)
				#print(b)
				for l in range(len(b)):
					del invader[b[0]]
				print("bomb " + str(a))

			elif inputList[0] == 4:
				if len(invader) < inputList[1]:
					print("distance -1")
				else:
					print("distance "+str(invader[inputList[1]-1]))

			#print(invader)
		print("end")