Having returned to the crazy house from December 2007, this time we just want to know how well we can move between the rooms connected by Portals.

The input file DATA5.txt will contain two lines with one integer value each, R,C; 0 < R, C <= 20, representing the number of Rows and Columns that make up the floor plan. Followed by R lines, showing the floor plan layout, where:

• # - wall
• . - open space
• {a-j, A-J} - marking entrance and exit nodes of portals
• {1..5} - integers 1 to 5, marking points of interest

Lower case letters mark entrance nodes, while corresponding capital letters mark exit nodes. That is, one can enter at point j and exit at point J. There will be no more than 10 portals in the floor plan.

The goal is to figure out which of the points are reachable, when starting out from each of the 5 marked points.

The output file OUT5.txt will contain 5 lines. The first line corresponds to starting from point 1, second line from point 2, etc. The line will begin with the corresponding start node and a colon, followed by a set of integers, separated by a single space, in ascending order -- other points of interest reachable from the starting point. If no other point is reachable, the output line is just the "n:", with no trailing spaces.

Note: Portals could create loops. In the sample below, room 1 leads to room 2, and room 2 has a path back to room 1. Please take care to avoid infinite loops, as those take a long time to execute.

10
11
..#.1..F#Af
..#.ea..#.2
###########
5.b.#BE#..4
....#c3#.C.
###########
.........#.
.d...D...#.
##########.
...........
        

1:2 3 4
2:1 3 4
3:4
4:
5:3 4