Water Cascade in Container‐Pipe Networks

While surfing online, Slavko came across an advertisement showing a system of containers interconnected by pipes. The system is represented as a matrix with N rows and M columns. In the matrix:

• Container outlines are drawn with + (at the four corners), - (for horizontal edges) and | (for vertical edges). Each container is rectangular. Note that if a container and a pipe meet, the container outline characters dominate.
• Inside each container (in an arbitrary location) there is a string of digits identifying the container’s label. All other cells are filled with a dot (.).
• All containers except the one labelled 1 have exactly one supply pipe entering from above. The supply pipe is represented by a vertical bar (|) immediately above a part of the container’s top outline.
• A container may have zero or more discharge pipes leaving from its lateral (left or right) sides. The discharge pipe exit is indicated by a horizontal dash (-) immediately adjacent to the container side. In each container, the discharge exits appear in different rows.
• Pipes are drawn with - and | characters and directly connect one container to another. The pipes do not branch or merge and do not intersect. Moreover, when traveling from the source container to the destination container the pipe’s row index never decreases (that is, the pipe either stays on the same row or goes to a lower row).

When water is poured into container 1, it begins filling up. A container fills until it is full; as soon as the water level reaches the level of one of its discharge exits it flows through that pipe and completely fills the connected container. Only after the connected container is filled does water resume filling the previous container so that additional discharge pipes (if any) may be activated. In other words, the water flow cascades from container to container.

Your task is to determine the order in which the containers get filled. Output the container labels in the order they become full.

Note:

• Every + is guaranteed to have exactly one adjacent horizontal character (-) on its left or right and exactly one adjacent vertical character (|) above or below; all other neighboring cells (up, down, left, right) contain ..
• The only times a pipe character appears adjacent to a container outline is when the pipe enters or exits a container.

Input/Output Format: See below.

inputFormat

The first line contains two integers N and M (1 ≤ N, M ≤ 300), the number of rows and columns of the matrix. The following N lines each contain a string of M characters representing the system.

outputFormat

Output a single line containing the labels of the containers in the order they get filled, separated by a single space.

sample

13 25
.........................
.........................
..+-------+..............
..|..1....|..............
..|.......|-----.........
..|.......|...............
..+-------+..............
...............|.........
............+-------+....
............|...2...|....
............|.......|....
............|.......|....
............+-------+....

1 2