Straightest Paths 

A digitized map is represented on a two dimensional grid as a set of points enclosed within a contour. The closed contour of the map (which can be of any rectangular shape) and the obstacles on the map (inside the contour) are marked using the character `X'. The free points on the map are designated by spaces. There are exactly two start-stop points on the map which are marked using the character `@'. The start-stop points cannot appear outside the map or on the contour of the map. There are no other points on the map except free points (spaces), obstacles (X) and start-stop points (@).

A path between two map points runs vertically and/or horizontally through the free points on the map (inside the map contour). The length of the path is the number of points the path runs through, including the start-stop points. The turns of the path are the direction changes while traversing the path.

Input and Output 

Write a program that, for each map read from a text file, finds all possible shortest paths with the minimum number of turns between the start-stop points on the map and marks the points of these paths using the character `#'. All paths are marked on the same map. The start-stop points preserve their initial markings. For example, the first map in sample below has 6 shortest paths of 32 points long and with 3 turns each.

Each map is terminated by a line full of underscores `_'. There are at most 40 lines and at most 80 characters in a line for each map, including the termination line. The lines can be of different length. Input data are correct.

The standard output file contains the maps with the marked paths. Each map is output in the same format it is read from the input file, including the termination line, and is preceded by a line which specifies the number of shortest paths, their length and turns as shown in the sample output.

Sample Input 

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X           X             @  X
X                   X        X
X                            X
XXXXXX          X            X
X               X            X
X        X              XXXXXX
X@       X              X
XXXXXXXXXXXXXXXXXXXXXXXXX
______________________________
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X                            X
X        @@             XXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
______________________________

Sample Output 

6 paths, 32 points, 3 turns
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X           X#############@  X
X            ###    X     #  X
X     #####################  X
XXXXXX###    ###X            X
X###############X            X
X#    ###X              XXXXXX
X@#######X              X
XXXXXXXXXXXXXXXXXXXXXXXXX
______________________________
1 paths, 2 points, 0 turns
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X                            X
X        @@             XXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
______________________________