题目描述

《迷失的地球》是一款很好玩的塔防类游戏。小 B 最近就迷上了这款游戏。然而小 B 又是一个很强势的人，他很不想玩游戏输掉，所以他想让你写一个程序帮忙算一下某一局游戏的结果和详细信息。小 B 已经知道了游戏的运行规则和相关信息，你能帮帮他吗？

游戏的相关信息:

1. 地图： 游戏的地图是一个 $n×m$ 的矩阵，设左上角坐标为 $(1,1)$。

   地图以字符矩阵的形式给出，比如 $n=m=5$ 的情况：

   S1###
   001##
   #0###
   #0002
   ###0T
   

   矩阵中第 $i$ 行第 $j$ 列的字符表示 $(i,j)$ 的情况。不同的字符对应的情况如下：

   • #：普通地图格点。
   • $0$：怪物通过的路线。
   • $1\sim 9$：防御塔。
   • $S$：怪物的生成点。
   • $T$：你的基地，即游戏的目的要防止怪物进入基地。

   输入数据保证地图合法，即地图上有且只有一个 $S$ 和一个 $T$，$S$ 到 $T$ 有且只有唯一的路线。

2. 怪物： 小 B 会给出一个怪物的生成队列，表示怪物的出现顺序。

   若队列不为空，则每一秒将会从队头取出一个新的怪物放在 $\text{S}$ 处。

   我们用两个整数来描述怪物的相关信息：

   • $\text{blood}$：怪物的血量。当血量小于等于 $0$ 时怪物死亡，从地图上消失。
   • $\text{speed}$：怪物的移动速度。每回合怪物将会沿着行进路线向 $\text{T}$ 移动 $\text{speed}$ 个单位。如果 $\text{speed}=0$ 那么怪物将被定在原地无法移动。如果移动后将超过 $T$ 处，那么视为到达了 $\text{T}$ 处。

3. 防御塔: 整个地图上最多会出现 $\text{t} ( 1\leq t\leq 9)$ 种不同的防御塔，用字符 $1\sim 9$ 在地图上表示。

   为了简化题目，我们假定小 B 不会在游戏过程中建造新的防御塔。所有防御塔在开始前就已经建造好了。我们用三个整数来描述每种防御塔的相关信息:

   • $\text{damage}$：表示该防御塔击中怪物后将对怪物造成的伤害。
   • $\text{distance}$：表示该防御塔能攻击到的最远距离。如果怪物与塔之间的直线距离不超过 $\text{distance}$，表示该塔可以攻击到该这个怪物。
   • $\text{type}$：表示该防御塔的攻击类型。
   • 若 $\text{type}=0​$ 表示该防御塔为普通攻击类型，即对单个怪物造成伤害。
   • 若 $\text{type}=1$ 表示该防御塔为范围性伤害，在对当前瞄准的怪物造成伤害的同时还会对该怪物周围距离不超过 $1$ 的怪物造成伤害。
   • 若 $\text{type}=2$ 表示该防御塔为直线型伤害，在攻击时将会生成一条连接该防御塔和当前瞄准的怪物的直线。直线可以向两端无限延伸，并且将对所有与直线距离不超过 $1$ 的怪物造成伤害。值得注意的是，虽然直线能够打到很远处的怪物，但是这种防御塔必须在有怪物离它不超过 $\text{distance}$ 时才能找到攻击目标发动攻击。
   • 若 $\text{type}=3$ 表示该防御塔为普通攻击类型，即对单个怪物造成伤害，并且会使命中的怪物的速度永久减少 $1$。但是减速效果在一个怪物身上最多只能生效一次，无法叠加。

为了防止歧义，我们定义防御塔选取目标的方式:

若当前有攻击目标，并且目标没有死亡、在攻击范围之内，那么将保持当前怪物作为目标。

若当前目标不合法（目标怪物死亡、超出攻击范围）或是没有攻击目标，将从攻击范围内的怪物中选取最靠前的一个（此处最靠前的定义为在怪物移动路径上里离 $\text{T}$ 点最近），若有多个则选取血量最少的一个，若还有多个则选取最早生成的一个。

为了简化题目，我们假定游戏为回合制，一秒为一个回合。对于每个回合，严格按照顺序有如下几个阶段：

1. 怪物生成阶段：若队列不为空，则取出怪物生成队列队头处的怪物放在 $\text{S}$ 处。

2. 防御塔锁定阶段：所有防御塔按照规则选取目标。

3. 防御塔攻击阶段：所有防御塔同时对自己的目标发动攻击。

4. 伤害结算阶段：将所有怪物的血量减去所受的攻击力，并将死亡的怪物清除。

5. 怪物移动阶段：地图上存在的怪物向前移动。

6. 回合结束阶段：若某个怪物处于 $\text{T}$ 处，则将该怪物移除并视为基地遭到一次攻击。

你的基地共有 $10$ 点血量，每遭到一次攻击则血量减 $1$。如果某回合结束后你的基地血量小于等于 $0$，则游戏结束，小 B 失败。如果场上没有任何怪物并且怪物生成队列为空，那么游戏结束，小 B 胜利。输入数据保证不会有游戏无法结束的情况。

输入格式

第一行有两个整数 $n,m\ (n,m\leq 10)$，意义如题目中所述。

接下来的 $n$ 行每行有一个长度为 $m$ 的字符串，描述地图。

接下来一行有一个整数 $\text{t}$，意义如题目中所述。

接下来 $\text{t}$ 行，每行三个整数 $\text{damage,distance,type}$，描述防御塔。

接下来一行有一个整数 $\text{q} (q\leq 50)$，表示怪物生成队列的长度。

接下来 $\text{q}$ 行，每行两个整数 $\text{blood,speed}$，描述队列中的每个怪物。

输出格式

第一行两个整数，表示游戏结束时的回合数和游戏结束时基地的剩余血量。

第二行描述游戏的结果。若小 B 胜利，输出 Victory!，否则输出 Xiao B is SB!。

接下来 $\text{q}$ 行，按照输入顺序描述每个怪物的状态:

若该怪物死亡，则输出 Died in round {死亡的回合数}。

若该怪物到达你的基地，则输出 Arrived your base in round {到达的回合数}。

若该怪物在游戏结束时还未生成或是还在地图中，则输出 The game has been over!。

5 5
S1###
001##
#0###
#0002
###0T
2
1 1 0
1 2 2
3
3 1
3 1
5 1

10 10
Victory!
Died in round 3
Died in round 4
Died in round 10

2 2
S0
1T
1
1 2 0
10
10 1
10 1
10 1
10 1
10 1
10 1
10 1
10 1
10 1
10 1

11 0
Xiao B is SB!
Arrived your base in round 2
Arrived your base in round 3
Arrived your base in round 4
Arrived your base in round 5
Arrived your base in round 6
Arrived your base in round 7
Arrived your base in round 8
Arrived your base in round 9
Arrived your base in round 10
Arrived your base in round 11