题目描述

bwgg 最近迷上了开盒子。

一天，他在微信上发现了一个小游戏，通关就能领取大量盒子，他兴高采烈地打开游戏，然后就卡关了。

bwgg 用他的智慧想出了一个一劳永逸的办法：写一篇代码解决问题，但他讨厌大模拟，于是他决定让你写。

如果你能帮他解决这个问题，他就能帮你穿越回高中，弥补遗憾也好什么也好。

在小游戏《劫营保卫战》中，玩家需要在限定步数内在不被发现的前提下消灭所有敌人然后抵达营帐。

玩家每步可以向上下左右任一方向移动，每次移动会前进至所选路线的终点。

如果终点是障碍物或营帐，玩家会停留在它前面；如果终点是敌人，玩家会消灭敌人并停留在敌人之前所在的位置；但是踏入或经过敌人前方（红色危险区域）将被敌人发现，过关失败并且直接结束。

$\textbf{当场上没有敌人时}$，如果移动终点是营帐，玩家会进入营帐，过关成功。

以下是一个示例关卡：

上图中，如果直接向下移动，会被发现导致过关失败。

一种可行的方案是"右下左（击杀敌人）上右（击杀敌人）下"，使用 $6$ 步通关。

如果你认为刚才那关太简单，那么还有一关：

一种方案是"右下左上左上右右下下左上右上左上左上右上右右左"，使用 $23$ 步通关。

现在，给定一张地图，游戏要求你在指定的步数内通关，请你构造出一个合法的路径方案。如果有多种合法路径，输出其中一种即可。

输入格式

第一行输入三个整数 $n \enspace m \enspace p$ $( n,m \leq 12,p \leq 30)$ ，表示地图的长度和宽度以及步数限制。

接下来输入 $n$ 行，每行 $m$ 个字符，表示初始地图。

在地图中，$\textbf{+}$ 表示玩家初始位置，$\textbf{=}$ 表示该格为营帐，$\textbf{x}$ 表示该格为障碍物，$\textbf{w}$ (上) $\textbf{a}$ (左) $\textbf{s}$ (下) $\textbf{d}$ (右) 表示该格为敌人以及他的朝向。

数据保证敌人的数量不超过 $10$ 个，保证有解，以及保证地图四周均被障碍物 $\textbf{x}$ 包围。

输出格式

第一行输出一个不大于 $p$ 的整数 $ans$ ,表示你使用的步数。

第二行输出一个长度为 $ans$ 的字符串，表示你的方案。

字符串仅由小写字母 $\textbf{wasd}$ 构成，表示向上/左/下/右移动，你过关后的多余操作将被忽略。

样例

7 7 6
xxxxxxx
x...sxx
x+.x..x
x.....x
x...=.x
xw....x
xxxxxxx

6
dsawds

12 9 23
xxxxxxxxx
x=...sd.x
x...x..xx
xw..axx.x
xx.x..x.x
x..d....x
x..x..x.x
xw....xsx
xx....x.x
x.+...x.x
x..a.d..x
xxxxxxxxx

23
dsawawddssawdwawawdwdda

样例解释

如果你和 bwgg 一样充满智慧并且讨厌大模拟，你可以靠自己解决这些问题。（确信）

本题共有六个评测点，你可以在点击这里下载所有的输入数据，然后用一个简单的程序对每组数据输出你的答案。