Painting Floors

My floor is a rectangle of squares one metre on a side, and some of those squares hold furniture. I bought 1000 cans of experimental paint to cover the rest of it myself. The manual explains what the experiment is.

Pour a whole can onto one square. The paint fills that square, then spreads along the same row and the same column, and it stops when it reaches a piece of furniture or the edge of the floor.

One can therefore paints the whole horizontal strip of bare squares that contains the poured square, and the whole vertical strip of bare squares that contains it.

In the left room the paint is poured in the third row and the second column, and it fills every coloured square. In the right room the paint is poured on the same square, but it stops at the black square of furniture.

You cannot pour paint onto furniture. A painted square never blocks a later pour, and painting the same square twice is allowed. The goal is to paint every square that holds no furniture, using at most 1000 cans.

The first line has two integers m and n ($1 \le m \le 500$, $1 \le n \le 500$), the number of rows and the number of columns of the floor. Each of the next m lines has n characters and describes one row. The character x is a piece of furniture and the character . is a bare square. The floor holds at most 500 pieces of furniture.

Many pouring plans paint the whole floor. Print this one.

Inside a single row, call a group of consecutive bare squares a strip when it can be extended neither to the left nor to the right. Every bare square belongs to exactly one strip of its own row. Pour one can at the leftmost square of every strip.

Print one line per can, holding the row and the column of the square it is poured on, separated by a space. Rows are numbered from 1 at the top and columns from 1 at the left. Sort the lines by row from top to bottom, and inside one row by column from left to right. This plan paints every bare square and never uses more than 1000 cans. Print nothing when the floor holds no bare square.