题目背景

机器人小 $\alpha$ 喜欢做游戏，机器人小 $\beta$ 喜欢玩游戏。

题目描述

现在，它们正在玩一个叫作推箱子的游戏！

机器人小 $\beta$ 为关卡制定了一个用字符串表示的移动路径：

身为机器人小 $\alpha$，你需要构造一个 $n\times m$ 的地图：

注意每个位置的东西只能是以上四种之一。

机器人的初始位置是给定的，方向朝上，地图外都是墙。

小 $\beta$ 完成移动后，所有箱子都必须移动过，小 $\alpha$ 需要让这个地图的箱子数最多，且小 $\beta$ 每步操作都合法。

以下给出所有不合法的操作：

小 $\alpha$ 需要一份程序来完成这份工作。

输入格式

本题有多组数据。

第一行一个正整数 $T$ 表示数据组数。

对于每组数据：

• 第一行两个整数 $n,m$。
• 第二行三个整数 $x,y,k$。
• 第三行一个长度为 $k$ 的字符串 $s$。

输入的数据含义如下：

• $n$ 和 $m$ 代表需要构造的地图的大小为 $n$ 行 $m$ 列。
• $x$ 和 $y$ 代表机器人的初始位置在从上往下第 $x$ 行从左往右第 $y$ 列。
• $k$ 代表移动路径的长度，$s$ 代表移动路径。

本题数据量较大，请使用较快的读写方式。

输出格式

对于每组数据，你需要给出一个 $n\times m$ 的地图代表你构造的地图，格式如题目描述所述。

所有最优的答案都可以得分。

1
3 4
2 2 17
DWSAWDWSSDWAWDWAW

..S.
SXS.
..S.

1
3 4
3 4 9
WSAWWDWDW

|.|.
|SSS
..SX

1
3 4
2 1 8
DWASDWAW

||.|
XS.|
|.S.

2
5 4
5 1 9
WDWAWDWAW
5 19
5 8 12
DDSAADDADADW

....
..S.
.SS.
SS..
X...
.........||||||||||
.........||......||
||||||...||......||
||..||...||......||
||||||.X.||||||||||

提示

部分样例有其他正确答案。

「数据范围」

本题开启 Special Judge 与捆绑测试。

一个测试点内，如果对于每组数据你的箱子数是最多的，且方案合法，你才能获得该测试点的分数。

只有通过一个子任务内的所有测试点才能得到该子任务的分数。

对于所有测试数据，保证：

• $1\leq n,m\leq 2000$，$1\leq \sum nm\leq 4\times 10^6$。
• $1\leq x\leq n$，$1\leq y\leq m$。
• $1\leq k,\sum k\leq 10^6$。
• $s_i\in\{\texttt{W},\texttt{A},\texttt{S},\texttt{D}\}$。
• 小 $\beta$ 的移动在空旷地图下一定合法。

• 特殊性质 A：前进和后退的总次数不超过 $20$ 次，且 $x=y=23$。
• 特殊性质 B：$s_i\in\{\texttt{W},\texttt{A},\texttt{D}\}$，且只会朝两个方向前进。
• 特殊性质 C：可放箱子的最大数量为 $0$ 或 $1$。

尽管比赛中不会返回，我们仍将告诉你 Special Judge 会返回的对应信息，优先级递减。

• Error: 1：出现规定以外的字符。
• Error: 2：出生点不在正确的位置。
• Error: 3：机器人无法前进。
• Error: 4：机器人无法后退。
• Error: 5：有箱子没有被推动过。
• Error: 6：箱子数不是最多的。
• Correct：测试点通过。