바닥 칠하기

내 방 바닥은 한 변이 1미터인 정사각형 칸으로 이루어진 직사각형이고, 그중 몇 칸에는 가구가 놓여 있다. 나머지 칸을 직접 칠하려고 실험용 페인트 1000통을 샀다. 설명서에는 무엇이 실험적인지 이렇게 적혀 있다.

한 통을 통째로 한 칸에 부으면 그 칸이 칠해지고, 페인트가 같은 행과 같은 열을 따라 번진다. 가구를 만나거나 바닥 끝에 닿으면 거기서 멈춘다.

그러므로 한 통은 페인트를 부은 칸이 속한 가로 방향 빈칸 구간 전체와 세로 방향 빈칸 구간 전체를 칠한다.

왼쪽 방에서는 3행 2열에 페인트를 부어 색이 칠해진 칸이 모두 칠해진다. 오른쪽 방에서는 같은 칸에 부었지만 검은 칸에 놓인 가구에서 페인트가 멈춘다.

가구가 놓인 칸에는 페인트를 부을 수 없다. 이미 칠한 칸이 나중에 부은 페인트를 막지는 않고, 같은 칸을 여러 번 칠해도 된다. 가구가 없는 칸을 1000통 이하로 모두 칠하는 것이 목표다.

첫째 줄에 바닥의 행 개수 m과 열 개수 n이 주어진다 ($1 \le m \le 500$, $1 \le n \le 500$). 다음 m개 줄에는 각각 n개의 문자가 주어지며 한 행을 나타낸다. 문자 x는 가구, 문자 .은 빈칸이다. 가구는 최대 500개다.

바닥 전체를 칠하는 방법은 여러 가지지만, 다음 한 가지를 출력한다.

한 행 안에서 연속한 빈칸의 묶음이 왼쪽으로도 오른쪽으로도 더 늘어날 수 없으면 이를 구간이라고 하자. 빈칸은 저마다 자기 행의 구간 하나에만 속한다. 각 구간의 가장 왼쪽 칸에 페인트를 한 통씩 붓는다.

한 통마다 한 줄씩, 페인트를 붓는 칸의 행 번호와 열 번호를 공백으로 구분해 출력한다. 행 번호는 위에서부터 1, 열 번호는 왼쪽에서부터 1이다. 줄은 행 번호가 작은 것부터, 같은 행에서는 열 번호가 작은 것부터 정렬한다. 이 방법은 빈칸을 모두 칠하고 1000통을 넘지 않는다. 빈칸이 하나도 없으면 아무것도 출력하지 않는다.