题目背景

$$\color{orange}「死んだ変数で繰り返す」\\ 「数え事が孕んだ熱」 \\ 「どこに送るあてもなく」 \\ 「あわれな独り言を記している」 \\ ——いよわ《熱異常》\\ $$

题目描述

已知在一片$n×n$区域里，有若干人需要逃生。用s表示这个点上有一个人，用x表示这个点上没有人。同时，这片区域里还会有机器人，用o表示。救一个人需要 $m$ 分钟，一共有 $t$ 分钟用来救人，空房子不需要救。同时，也会出现 $r$ 种自然灾害灾害，会提供这个灾害的坐标$(x,y)$ 。

火山：每 $s$ 分钟向上蔓延一格，蔓延到的点里上的人无法逃生。

区域地震：救人的时间 $m$ 增加 $l$ 分钟。

爆炸：会波及上下左右的格子，波及到的点里上的人无法逃生。

已知会发生的灾难，并且机器人不受灾难的影响。请求出救出所有人所用的最短时间，并尽量救人，不救机器人。

输入格式

第一行，三个正整数，分别是$n$、$m$和$t$。
随后 $n$ 行，每行有 $n$ 个点，只会出现s、x、o。
随后，一个正整数$r$，后面$r$行，每行一个字符串，和若干个整数。

eru:火山喷发，后面跟着三个正整数，分别是$x$、$y$和$s$。

qud:区域地震，后面跟着三个正整数，分别是$x$、$y$和$l$。

bom:爆炸，后面跟着两个正整数，分别是$x$和$y$。

输出格式

如果在$t$分钟之内能全部救出，输出All和救出所有人和机器人所用的最短时间；

如果$t$分钟之内救不出全部，输出No。

然后输出救出人和机器人的数量。

样例

5 1 10
ssxxo
ssoox
ooxxx
xxxxx
4
eru 1 5 1
eru 2 2 3
qud 5 5 1
bom 3 3

All 1
6 2

提示

对于$100\%$的数据：

$2≤x,y≤n<100$

其余数据不超过int数据范围。