클릭베이트

슬라브코는 인터넷을 돌아다니다가 물통과 관으로 이루어진 장치를 보여 주는 광고를 발견했다. 광고에는 "1번 물통에 물이 차기 시작하면 물통이 가득 차는 순서를 맞혀 보세요."라고 적혀 있었다. 이런 장치의 예는 아래 그림과 같다.

장치는 1번부터 K번까지 번호가 붙은 물통 K개로 이루어지고, N행 M열짜리 문자 행렬로 나타낸다. 물통은 모두 직사각형이며, 물통과 관의 윤곽선은 다음 문자로 그린다.

• 윤곽선의 가로 부분은 -
• 윤곽선의 세로 부분은 |
• 가로 부분과 세로 부분이 만나는 자리는 +

물통과 관이 만나는 자리는 예외로, 이 자리에서는 물통의 윤곽선이 우선한다.

각 물통 안의 어딘가에는 그 물통의 번호를 나타내는 숫자 문자열이 하나 있고, 행렬의 나머지 칸은 모두 .(마침표)이다.

1번 물통을 뺀 모든 물통에는 물이 들어오는 관이 정확히 하나 있고, 이 관은 물통의 윗변으로 들어온다. 1번 물통에는 물이 들어오는 관이 없다.

물통에는 물이 빠져나가는 관이 여러 개 있을 수도 있고 하나도 없을 수도 있으며, 이 관은 물통의 옆변으로 나간다. 한 물통에서 물이 빠져나가는 자리는 행렬에서 서로 다른 행에 있다.

관은 두 물통을 곧바로 잇는다. 관을 나누거나 여러 관을 하나로 합치는 일은 없고, 두 관이 서로 교차하지도 않는다. 관은 출발하는 물통에서 도착하는 물통으로 가는 동안 항상 다음 행으로 내려가거나 같은 행에 머무르며, 이전 행으로 되돌아가지 않는다. 그래서 물은 한 물통에서 다른 물통으로 막힘없이 흐른다.

물은 물통이 가득 찰 때까지 들어온다. 물의 높이가 물이 빠져나가는 관의 높이에 이르면, 그 관이 이어진 물통이 가득 찰 때까지 물이 그 관으로 흐른다.

물통이 가득 차는 순서를 구하라.

참고할 점

• 입력 자료에서 문자 +의 왼쪽이나 오른쪽 중 정확히 한 칸이 -이고, 위쪽이나 아래쪽 중 정확히 한 칸이 |이며, 상하좌우로 붙어 있는 나머지 칸은 모두 .(마침표)이다.
• 행렬에서 관이 물통의 윤곽선과 붙어 있는 자리는 관이 물통으로 들어가거나 물통에서 나오는 자리뿐이다. 다시 말해 관은 물통 바로 옆을 지나가지 않는다. 물이 들어오는 관의 입구는 물통 위쪽의 | 문자이고, 물이 빠져나가는 관의 출구는 물통 옆변 바깥의 - 문자이다.

첫째 줄에 행렬의 크기 N과 M이 주어진다. ($1 \le N, M \le 1000$)

다음 N개 줄에는 장치를 나타내는 문자가 한 줄에 M개씩 주어진다.

K개 줄을 출력한다. i번째 줄에는 i번째로 가득 차는 물통의 번호를 출력한다. 답은 항상 있고 하나뿐이다.

첫 번째 예제를 설명하면 다음과 같다.

1번 물통에 물이 차기 시작한다.

1번 물통의 물 높이가 올라가다가 2번 물통으로 이어지는 관의 높이에 이른다. 2번 물통이 가득 찰 때까지 물이 그 관으로 흐른다.

그다음 1번 물통의 물 높이가 계속 올라가 3번 물통으로 이어지는 관의 높이에 이르고, 3번 물통이 가득 찬다.

마지막으로 1번 물통의 물 높이가 계속 올라가 1번 물통이 가득 찬다.