A team of up-to four robots is going to deliver parts in a factory floor. The floor is organized as a rectangular grid where each robot occupies a single square cell. Each robot is represented by an integer from 1 to 4 and can move in the four orthogonal directions (left, right, up, down). However, once set in motion, a robot will stop only when it detects a neighbouring obstacle (i.e. walls, the edges of the factory or other stationary robots). Robots do not move simultaneously, i.e. only a single robot moves at each time step.

The goal is to compute an efficient move sequence such that robot 1 reaches a designed target spot; this may require moving other robots out of the way or to use them as obstacles for “ricocheting” moves.

Consider the example given above, where the grey cells represent walls, X is the target location and 1, 2 mark the initial positions of two robots. One optimal solution consists of the six moves described below.

Note that the move sequence must leave robot 1 at the target location and not simply pass through it (the target does not cause robots to stop — only walls, edges and other robots).

Given the description of the factory floor plan, the initial robot and target positions, compute the minimal total number of moves such that robot 1 reaches the target position.

Input

The first line contains the number of robots n (1 ≤ n ≤ 4), the width w and height h (w, h ≥ 1, max(w, h) ≤ 10) of the factory floor in cells, and an upper-bound limit l (1 ≤ l ≤ 10) on the number of moves for searching solutions. The remaining h lines of text represent rows of the factory floor with exactly w characters each representing a cell position:

• W a cell occupied by a wall;
• X the (single) target cell;
• 1, 2, 3, 4 initial position of a robot;
• ’.’ an empty cell.

Output

The output should be the minimal number of moves for robot 1 to reach the target location or NO SOLUTION if no solution with less than or equal the given upper-bound number of moves exists.