我们勇敢的旅行者到达了一个海盗埋藏着宝藏的岛屿。然而,当船即将靠岸时,船长发现有老鼠吃了一块藏宝图。
藏宝图可以表示为一个大小为 n × m 的矩形。每个单元格代表一个岛屿的正方形(正方形的边长等于一英里)。有些细胞代表大海,它们是无法穿透的。所有其他单元都是可穿透的(即可用),其中一些包含当地景点。例如,山上的大树或岩石中的洞穴。
此外,该映射还有一组k条指令。每条指令的形式如下:
“沿 y 方向步行 n 英里”
可能的方向有:北、南、东、西。如果您仔细遵循这些说明(您应该一一完成所有这些说明),那么您应该准确地到达埋藏宝藏的地方。
不幸的是,船长不知道从哪里开始执行指示——因为地图的那一部分已经丢失了。但船长清楚地记得这个地方有一些当地的景观。此外,船长知道整条路都要经过岛上的可穿透的广场。
船长想知道哪些景点值得检查。他请你帮助他。
输入
第一行包含两个整数 n 和 m (3 ≤ n, m ≤ 1000)。
然后n行,每行包含m个整数——岛屿地图的描述。 “#”代表大海。保证矩形周边的所有单元格都是海洋。 “。”代表没有任何瞄准具的可穿透正方形,瞄准具用大写拉丁字母从“A”到“Z”标记。并非所有字母都可以使用。然而,可以保证地图上至少有其中之一。所有当地景点都标有不同的字母。
下一行包含数字 k (1 ≤ k ≤ 105),其后是 k 行。每行描述一条指令。每条指令都具有“dir len”的形式,其中dir代表方向,len代表要走的路的长度。 dir 可以分别取值“N”、“S”、“W”和“E”,分别表示北、南、西和东。此时,上为北,下为南,左为西,右为东。 len 是 1 到 1000 之间的整数。
输出
按字母顺序将所有满足指令的本地景点打印为不带任何分隔符的字符串。如果没有合适的瞄准器,请打印“无解决方案”,不带引号。
示例
输入 #1
6 10 ########## #K#..##### #.#..##.## #..L.#...# ###D###A.# ########## 4 N 2 S 1 E 1 W 2
输出 #1
AD
输入 #2
3 4 #### #.A# #### 2 W 1 N 2
输出 #2
no solution