题目描述

While surfing online, Slavko came across an ad displaying a system of containers and pipes (an example of such system is illustrated in the image below) with the message: “If container 1 starts filling up with water, determine the order in which the containers get filled up.”

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 tests).

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.

输入格式

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.

输出格式

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.

题目大意

在上网的时候，Slavko遇到了一个广告，这个广告上面有一个由容器和管道组成的系统（如图是一个系统的例子）和一行字：“如果往编号为1的容器里注水，请确定这些容器被注满水的顺序。” 这个系统包含K个编号为1到K的容器，并且我们可以用一个N×M的矩阵来描述它。这些容器的形状为长方形。容器和管道的轮廓将用这些字符表示：

• 如果字符为‘-’，那么这个位置是容器和管道的轮廓的水平部分。
• 如果字符为‘|’，那么这个位置是容器和管道的轮廓的垂直部分。
• 如果字符为‘+’，那么这个位置同时是容器和管道的轮廓的水平和垂直部分。（即容器的四个角，管道的拐弯部分），一个例外是容器与管道的相交部分，在这个位置不使用+。 在每一个容器内的某个位置内，都存在一个表示这个容器编号的数字串。矩阵内既不是容器和管道的轮廓，又不是表示容器编号的数字串的位置上的字符为'.'。 除了编号为1的容器以外，所有的容器的顶部都接入且只接入了一条可以使水进入容器的管道。编号为1的容器的顶部没有管道。 每个容器的侧面可以接入多条（也可以没有）可以使水流出容器的管道。没有两个可以使水流出容器的管道与容器的连接处在同一个高度。 管道必须有方向的连接两个容器，这也就意味着一条管道不能在某些地方分成两条管道，或是两条管道交汇成一条管道，并且没有两条管道会相交。并且管道永远不会向上拐弯，所以可以保证管道里的水可以正常的向下流动并且流入对应接入的容器里。 水只能进入没有被装满水的容器。如果一个容器中的水位达到了可以使水流出的管道的高度，水将会流入这个管道的另一端所接入的容器里，直到那个容器满了为止。 请帮助Slavko确定这些容器被注满水的顺序。 请注意：
• 在矩阵中，每一个字符'+'都有且仅有一个'-'字符在其左边或右边与其相邻，并且有且仅有一个'|'字符在其上边或下边与其相邻。其余的与其相邻的字符将均为'.'。
• 在字符矩阵中，管道与容器轮廓相邻的唯一可能的位置是管道与容器连接的位置。换句话说，除了管道与容器连接的情况，管道不可能与容器相邻。在与容器连接的位置，管道使水流入容器的一端用'|'标识，使水流出容器的一端用'-'标识。

输入格式

第一行，两个整数N,M(1≤N,M≤1000)，表示矩阵的大小。 接下来的N行，每行M个字符，描述了如题目所述的容器系统。

输出格式

你必须输出K行。第i行表示第i个被注满水的容器的编号。输入保证存在唯一解。

说明

对于$70$的数据，满足N,M≤100。 样例1的解释： 开始向容器1注水。 容器1中的水位升高，并且在某个时刻达到通向容器2的管道的高度。水流进管道并最终流向容器2，直到容器2装满水为止。 此后，容器1中的水位继续升高，直到达到通向容器3的管道的高度，水流进管道并最终流向容器3，直到容器3装满水为止。 最后，容器1中的水位持续升高，直到容器1装满水。

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

2
3
1

8 10
..........
.......+-+
...+---|1|
...|...+-+
...|......
..+-+.....
..|2|.....
..+-+.....

2
1

提示

In test cases worth 70% of total points, it will hold N, M ≤ 100.

Clarification of the first test case:

Container 1 starts filling up with water.

The water level in container 1 grows, and in one moment reaches the level of the discharge pipe leading to container 2. The water flows through the pipe until container 2 fills up.

After that, the water level in container 1 keeps growing until it reaches the level of the discharge pipe leading to container 3, which fills up next.

Finally, the water level in container 1 keeps growing and the container fills up.