← 返回题目列表

AtCoder · wupc_07

G. 不倒翁大志

中文机器翻译题面 查看原题
 达摩落下机器人是一种可以自动进行达摩落下的机器人。机器人配有锤子,能够在指定高度精确地敲击积木。机器人的开发已进入关键阶段,终于决定进行实战测试。为了顺利进行测试,需要编写如下程序。

問題

 在初始状态下 N 考虑积有个积木的达摩落下。每个积木的高度从下往上数,a_{1} a_{2} ... a_{N} 是如此。同时,机器人的锤子半径为 H 。接下来会给出如下 M 个查询,请按顺序处理。

 “积木添加(add)”查询:在当前达摩最上方,新增加高度为 arg_{i} 的积木。对于此查询,无需输出。

 “挑战(challenge)” 查询:锤子的中心高度 arg_{i} 状态下尝试让达摩跌落。输出对机器人的指示以执行此动作。
 
 在这里,如果锤子跨越了 2 个或更多的积木,由于达摩会倒塌,需要停止机器人的动作。在这种情况下,输出 "stop"。如果指定的位置过高以至于锤子无法击中积木,则输出 "miss"。在这些情况下,对积木没有影响。
 
 其他情况下(锤子的位置正确时),输出 "go"。在这种情况下,机器人将在指定位置旋转锤子,从达摩上取下一个积木。堆叠在该积木上的积木将直接落下,积木的数量为 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