The engineers at VRI (Voltron Robotics Institute) have built a swarm of $n$ robots. Any two compatible robots that stands on the same grid can merge to form another composite robot.

We label the robots with number $1$ to $n$ $(n\le 9)$. Two robots are compatible if they have labels that are consecutive. Originally, each of the $n$ robot has one unique label. A composite robot that is formed after merging two or more robots is assigned two labels, consisting of the minimum and maximum label of the robots that merge into the composite robot.

For example, robot 2 can only merge with robot 3 or robot 1. If robot 2 merges with robot 3, a composite robot 2-3 is formed. If robot 2-3 merges with robot 4-6, a composite robot 2-6 is formed. The robot 1-$n$ is formed when all robots have merged.

The engineers place $n$ robots in a room consisting of $w\times h$ grids, surrounded by walls. Some grids are occluded and cannot be accessed by the robots. Each grid can hold one or more robots, and a robot always occupies exactly one grid. Initially, each robot is placed on a different grid.

The robots are rather primitive. They can move only in a straight line along either the x-axis or y-axis after being pushed by an engineer. After it is pushed in one of the four directions parallel to the x- and y-axis, the robot continues moving, in the direction it is pushed in, until it is blocked either by an occlusion or a wall. After the robot stops moving, it scans for other compatible robots occupying the same grid, and merge with any compatible robot it finds into a larger robot. The merging process continues until no further merging is possible.

To help the robots change direction, the engineers have placed rotating plates in some of the grids. The rotating plates can either rotate in a clockwise or anti-clockwise direction. A robot that moves into a grid with the rotating plate always changes its moving direction by 90 degree in the same direction as the rotating plate. If a robot is being pushed while resting on top of a rotating plate, it rotates by 90 degree before moving off in a straight line, in a direction perpendicular to the direction it is pushed in.

Only one robot can move at one time.

Your task is to find the minimum number of pushes such that all $n$ robots are merged together (if possible).

Input Specification

Your program must read from the standard input. The first line of the input file contains three integers, $n$, $w$, and $h$, separated by a space.

The next $h$ lines of the input file describe the room, each line contains $w$ characters. Each of these $w\times h$ characters represent a grid in the room.

A numeric character (1 to 9) indicates that there is a robot labeled with the corresponding number in the grid. A character x indicates that there is an occlusion in the grid. A character A or C indicates that there is a rotating plate in the grid. A indicates that the plate is rotating anti-clockwise. C indicates that the plate is rotating clockwise. All other grids are represented with a character .

Output Specification

Your program must write to the standard output, either a single number indicating the minimum number of pushes needed to merge all $n$ robots, or -1 if merging is not possible.

Subtasks

Your program will be tested on four sets of input instances as follow:

1. (10 points) The instances satisfy $n=2$, $w\le 10$, $h\le 10$, with no rotating plates.
2. (20 points) The instances satisfy $n=2$, $w\le 10$, $h\le 10$.
3. (30 points) The instances satisfy $n\le 9$, $w\le 300$, $h\le 300$.
4. (40 points) The instances satisfy $n\le 9$, $w\le 500$, $h\le 500$.

Sample Input

4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...

Sample Output

5

Explanation for Sample Output

The following 5 steps optimally merge the robot.

1. Push robot 3 rightward. The robot moves right, meets a rotating plate, turns anti-clockwise, and continues its movement up. The robot eventually stops in front of the wall.
2. Push robot 4 upward. The robot moves up, stops in front of the wall, and merges with robot 3 to form robot 3-4.
3. Push robot 2 upward. The robot moves up, meets a rotating plate, turns anti-clockwise, hits a wall and stops.
4. Push robots 2 rightward. The robot rotates anti-clockwise, moves up, stops at the corner, and merges with robot 1 to form robot 1-2.
5. Push robot 3-4 leftward. The robot moves left, stops at the corner, and merges with robot 1-2.