题目描述

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

游戏的相关信息:

1.地图:

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

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

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

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

• #: 普通地图格点。

• 0: 怪物通过的路线。

• 1~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~9在地图上表示。

为了简化题目，我们假定小 $\text{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失败。如果场上没有任何怪物并且怪物生成队列为空，那么游戏结束，小 $\text{B}$ 胜利。输入数据保证不会有游戏无法结束的情况。

输入格式

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

接下来的 $\text{n}$ 行每行有一个长度为 $\text{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!。

样例 1

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