DWITE Online Computer Programming Contest, December 2007, Problem 5

In an experiment gone horribly wrong, a number of portals have gotten installed in a house. The portals come in a directional variety, that is – one entrance and one exit node. Calculating the area of rooms has suddenly become a lot trickier.

The input will contain two lines with one integer value each, ~R, C~ ~(1 \le R, C \le 40)~, 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 rooms of interest

Lowercase 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 output will contain 5 lines. Each line will have an integer representing the area of a room of interest. First line should contain the area of room 1, second line of room 2, etc.

The area of the room is defined as ~1\ +~ number of adjacent open spaces. Portals, and areas of rooms they lead to, also add to the total area. The integer marker could appear anywhere inside the room. A portal could lead from one room of interest to another (it's possible for the sum of the area of rooms to be greater than the size of the house). If the portal exits within the same room, the area should not be counted twice.

Sample Input

10
11
1.#.2...#A.
..#.a...#..
###########
3.b.#B.#...
....#c.#.C.
###########
4........#.
.d...D...#.
##########.
..........5

Sample Output

4
14
18
18
14

Problem Resource: DWITE