CLCKBAIT - Clickbait

While surfing online, Slavko came across an ad displaying a system of containers and pipes.

The system consists of K containers denoted with numbers from 1 to K, and we can describe it using a matrix of characters with N rows and M columns.

The containers are in the shape of a rectangle​, and the outlines of the containers and pipes are shown with the following characters:

  • ‘-’ if it’s a horizontal part of the outline,
  • ‘|’ if it’s a vertical part of the outline, and
  • ‘+’ if it’s a spot where the horizontal and vertical parts of the outline connect. An exception is where the containers and pipes connect. In that case, the container outline dominates (see sample test).

In an arbitrary place within each container, there is a string of digits that represent the label of the container, and all the other fields in the matrix are equal to ‘.’ (dot).

All containers except the one labeled with 1 have exactly one supply pipe that enters the container in its upper side​. The container labeled with 1 does not have a supply pipe.

The containers can have multiple (also possible, zero) discharge pipes that leave the container out of its lateral side​. The places where discharge pipes leave a container will be in mutually distinct rows​ in the matrix.

The pipes directly connect two containers, which means that it is not possible to split the pipes or connect multiple pipes into one, and no two pipes will intersect. On their way, looking from the source to the destination container, the pipes always descend to the following row or stay in the same row. In other words, they never go back to the previous row, so the water can flow freely from one container to another.

The water enters a container until it is full. If the water level reaches the level of the discharge pipe, the water will flow through that pipe until the container the pipe leads into is filled up.

Help Slavko and determine the order in which the containers will fill up.

Please note​:

  • The test data is such that each character ‘+’ is surrounded with exactly one character ‘-’ to the left or the right side and exactly one character ‘|’ to the upper or lower side, and all other adjacent characters in directions up, down, left and right will be equal to ‘.’ (dot).
  • The only places where the pipe in the matrix is in a field adjacent to the container outline are the places where the pipe enters or exits the container. In other words, a pipe will never run right next to a container (except where it connects with the container). The entry for the supply pipe is labeled with the character ‘|’ above a container, whereas the exit of the discharge pipe is labeled with the character ‘-’ on the lateral side of a container.

Input

The first line contains two integers N and M (1 ≤ N, M ≤ 1000), matrix dimensions. The following N lines contain M characters describing the container system.

Output

You must output K lines. The i th line contains the label of the container that fills up i th . A solution will always exist and will be unique.

Example

Input:
12 13
..+--+.......
+-|..|.......
|.|.1|--+....
|.+--+..|....
|......+----+
+---+..|..2.|
....|..+----+
.+--+........
.|...........
+---+........
|.3.|........
+---+........

Output:
2
3
1

Added by:mdorcic
Date:2018-04-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:COCI 2017/2018 Round #7

hide comments
2021-07-04 17:45:55
can't pass after 9th TC.... any hint!!
2018-05-17 10:59:03 hanstan
I think you should give additional statement from the original question, which is “If container 1 ​starts filling up with water, determine the order in which the containers get filled up.”
2018-04-24 02:52:55
I donot lile long descreption in fact. But want to finally it;
2018-04-19 07:08:01
Best new problem in a long while! Enjoyed immensely, thank you.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.