一组最多四个机器人将在工厂地面上运送零件。工厂地面被组织成一个矩形网格，每个机器人占据一个单元格。每个机器人用 1 到 4 的整数表示，可以在四个正交方向（左、右、上、下）上移动。然而，机器人一旦开始移动，只有在检测到相邻障碍物（即墙壁、工厂边缘或其他静止的机器人）时才会停止。机器人不会同时移动，即在每个时间步长内只有一个机器人移动。

目标是计算出一个高效的移动序列，使得机器人 1 到达指定的目的地；这可能需要将其他机器人移开，或者利用它们作为“反弹”移动的障碍物。

考虑右侧给出的示例，其中灰色单元格代表墙壁，X 是目标位置，1 和 2 标记了两个机器人的初始位置。一个最优解由以下六步移动组成：

1 号机器人向上移动。

2 号机器人向右、向下和向左移动。

1 号机器人向下和向左移动。

请注意，移动序列必须使机器人 1 停在目标位置，而不能仅仅经过它（目标位置不会导致机器人停止——只有墙壁、边缘和其他机器人会）。

题目描述

给定工厂平面图的描述、机器人的初始位置和目标位置，计算机器人 1 到达目标位置所需的最小总移动步数。

输入格式

第一行包含机器人数量 $n$、工厂地面的宽度 $w$ 和高度 $h$（以单元格为单位），以及搜索解的移动步数上限 $\ell$。

接下来的 $h$ 行文本表示工厂地面的行，每行包含 $w$ 个字符，每个字符代表一个单元格位置：

• W：被墙壁占据的单元格；
• X：目标单元格（唯一）；
• 1,2,3,4：机器人的初始位置；
• .：空单元格。

数据范围

$1 \le n \le 4$ $\max(w, h) \le 10$ $w, h \ge 1$ $1 \le \ell \le 10$

输出格式

输出机器人 1 到达目标位置所需的最小移动步数。如果不存在步数小于或等于给定上限的解，则输出 NO SOLUTION。

样例

样例输入 1

2 5 4 10
.2...
...W.
WWW..
.X.1.

样例输出 1

6

样例输入 2

1 5 4 10
.....
...W.
WWW..
.X.1.

样例输出 2

NO SOLUTION