G - だるま落とし Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

　だるま落としロボットは自動でだるま落としをするロボットである．ロボットにはハンマーがついており，指定された高さで正確にブロックを叩くことができる．ロボットの開発が佳境に入り，いよいよ実践テストを行うことになった．テストをスムーズに進めるため，次のようなプログラムを書いて欲しい．

問題

　初期状態で N 個のブロックが積み上がっただるま落としを考える．それぞれのブロックの高さは下から数えて，a_{1}　a_{2}　...　a_{N} である．また，ロボットのハンマーの幅の半径を H とする．次のようなクエリが M 個与えられるので，順番に処理せよ．

　「ブロック追加(add)」クエリ : 現在のだるまの一番上に，新たに高さ arg_{i} のブロックを追加する．このクエリに対して出力を行う必要はない．

　「チャレンジ(challenge)」クエリ : ハンマーの中心が高さ arg_{i} である状態でだるまを落とそうとする．この動作に対するロボットへの指示を出力せよ．
　
　ここで，ハンマーが 2 つ以上のブロックにまたがってしまう場合は，だるまが崩れてしまうため，ロボットの動作を止める必要がある．そのような場合は，"stop" と出力せよ．指定された位置が高すぎてハンマーがブロックに当たらない場合は，"miss" と出力せよ．これらの場合は，ブロックに影響はない．
　
　それ以外の場合，(ハンマーの位置が正しい場合)，"go" と出力せよ．その場合，ロボットは指定された位置でハンマーを回転させ，ブロックを1つだるまから外す．そのブロックの上に積み上がっているブロックたちは，そのまま下に落下し，ブロックの数が 1 つ減っただるまができる．なお，ハンマーかただ1つのブロックにまたがる場合で，上面や下面がちょうどブロックの境目に接している場合でも，ロボットへは "go" と指示せよ．
　
図1. 初期配置
図2. addクエリ: 高さ arg_{i} のブロックを上に追加
図3. challengeクエリ: 高さ arg_{i} で叩く

入力

入力は以下の形式で標準入力から与えられる． 
N　M　H
a_{1}　a_{2}　...　a_{N}
operation_{1}　arg_{1}
operation_{2}　arg_{2}
...
operation_{M}　arg_{M}
  • 1 行目に初期状態のブロックの数 N(1 ≦ N ≦ 100,000) とクエリの数 M(1 ≦ M ≦ 100,000)，およびハンマーの半径 H(1 ≦ H ≦ 100,000) が半角スペース区切りで与えられる．
  • 2 行目には初期状態で積まれているブロックの高さ a_{i}(1 ≦ a_{i} ≦ 100,000) が半角スペース区切りで与えられる．
  • 3 行目～ M+2 行目にはクエリの情報が与えられる．
  • 各クエリは操作名( operation_{i} )と引数( arg_{i} )から成り，それぞれ半角スペース区切りで与えられる．各クエリは以下の条件を満たす．
    • operation_{i} = \{add, challenge\}
    • operation_{i} = addのとき，1 ≦ arg_{i} ≦ 100,000 を満たす．
    • operation_{i} = challengeのとき，H ≦ arg_{i} ≦ 1,000,000,000,000 を満たす．

出力

operation_{i} = challengeであるクエリに対する答えを与えられた順番に1 行ずつ出力せよ．
なお、最後には改行を出力せよ．

部分点

20 点分については，上記条件に加え，以下の条件を全て満たす．
  • 1 ≦ N ≦ 1,000
  • 1 ≦ M ≦ 1,000

入力例 1

3 10 3
10 10 10
challenge 5
add 20
challenge 10
challenge 15
add 1
add 9
challenge 31
challenge 38
challenge 50
challenge 40

出力例 1

go
stop
go
stop
go
miss
miss