VRI（Voltron Robotics Institute，伏特隆机器人研究所）的工程师们制造了一群机器人，总数为 $n$ 个。任何两个位于同一网格且兼容的机器人都可以合并成一个新的复合机器人。
我们将机器人编号为 $1$ 到 $n$ ($n \le 9$)。如果两个机器人的编号是连续的，则它们是兼容的。最初，每个机器人都有一个唯一的编号。两个或多个机器人合并后形成的复合机器人会被分配两个标签，分别由合并前各机器人编号的最小值和最大值组成。
例如，机器人 $2$ 只能与机器人 $3$ 或机器人 $1$ 合并。如果机器人 $2$ 与机器人 $3$ 合并，则形成复合机器人 $2-3$。如果机器人 $2-3$ 与机器人 $4-6$ 合并，则形成复合机器人 $2-6$。当所有机器人合并时，形成机器人 $1-n$。
工程师们将 $n$ 个机器人放置在一个由 $w \times h$ 个网格组成的房间里，房间四周有墙。有些网格是障碍物，机器人无法进入。每个网格可以容纳一个或多个机器人，且一个机器人始终精确占据一个网格。最初，每个机器人被放置在不同的网格中。
这些机器人非常原始。在被工程师推动后，它们只能沿 $x$ 轴或 $y$ 轴直线移动。在沿平行于 $x$ 轴或 $y$ 轴的四个方向之一被推动后，机器人会沿推动方向持续移动，直到被障碍物或墙壁阻挡。机器人停止移动后，会扫描同一网格内的其他兼容机器人，并与找到的任何兼容机器人合并成一个更大的机器人。合并过程会持续进行，直到无法再进行合并为止。
为了帮助机器人改变方向，工程师在一些网格中放置了旋转板。旋转板可以顺时针或逆时针旋转。进入带有旋转板网格的机器人总是会按照旋转板的旋转方向改变 $90^\circ$ 的移动方向。如果机器人在位于旋转板上时被推动，它会先旋转 $90^\circ$，然后沿垂直于推动方向的方向直线移出。
同一时间只能有一个机器人移动。
你的任务是找出使所有 $n$ 个机器人合并在一起所需的最少推动次数（如果可能的话）。
输入格式
程序必须从标准输入读取数据。输入文件的第一行包含三个整数 $n, w, h$，由空格分隔。
接下来的 $h$ 行描述了房间，每行包含 $w$ 个字符。这 $w \times h$ 个字符中的每一个都代表房间里的一个网格。
数字字符（'1' 到 '9'）表示该网格中有一个对应编号的机器人。字符 'x' 表示该网格中有障碍物。字符 'A' 或 'C' 表示该网格中有一个旋转板。'A' 表示该板逆时针旋转，'C' 表示该板顺时针旋转。'.' 字符填充所有其他网格位置。
输出格式
程序必须向标准输出写入一个数字，表示合并所有 $n$ 个机器人所需的最少推动次数；如果无法合并，则输出 -1。
子任务
程序将在以下四组输入实例上进行测试：
- (10 分) 实例满足 $n = 2, w \le 10, h \le 10$，且没有旋转板。
- (20 分) 实例满足 $n = 2, w \le 10, h \le 10$。
- (30 分) 实例满足 $n \le 9, w \le 300, h \le 300$。
- (40 分) 实例满足 $n \le 9, w \le 500, h \le 500$。
样例
样例输入 1
4 10 5 1......... AA...x4... ..A..x.... 2....x.... ..C.3.A...
样例输出 1
5
说明
以下 5 个步骤可以最优地合并机器人：
- 向右推动机器人 3。机器人向右移动，遇到旋转板，逆时针转向，并继续向上移动。机器人最终停在墙前。
- 向上推动机器人 4。机器人向上移动，停在墙前，并与机器人 3 合并形成机器人 3-4。
- 向上推动机器人 2。机器人向上移动，遇到旋转板，逆时针转向，撞到墙壁并停止。
- 向右推动机器人 2。机器人逆时针旋转，向上移动，停在角落，并与机器人 1 合并形成机器人 1-2。
- 向左推动机器人 3-4。机器人向左移动，停在角落，并与机器人 1-2 合并。