eolymp
bolt
Try our new interface for solving problems
Problems

Japanese crossword

Japanese crossword

Time limit 1 second
Memory limit 128 MiB

Phineas and Ferb decide to print their own newspaper. Almost everything is ready, it remains only to add some kind of puzzle to the end of the newspaper. The choice of the guys fell on a Japanese crossword puzzle.

Recall that the Japanese crossword is a puzzle, the purpose of which is to get a black and white checkered picture of the size n * m. The hidden Japanese crossword puzzle contains an empty field n * m, some cells of which need to be colored black. To the left of each line of the field is a sequence of numbers. These numbers correspond to the lengths of the segments of black cells in this line, listed from left to right. Similarly, above each column is written a sequence of numbers corresponding to the lengths of the black segments in that column, listed from top to bottom.

prb11091.gif

Phineas and Ferb have chosen a picture that should be the result of solving a crossword puzzle. Help them find sequences of numbers that should be written to the left of the rows and to the top of the columns.

Input data

The first line contains two integers n and m (1n, m100) - the size of the picture.

The next n lines contain m characters each describing the picture. White color is indicated by the symbol ".", and black by "#".

Output data

First print n lines describing the lines of the Japanese crossword from top to bottom. Each of them should start with the number of numbers in that line, and then those numbers themselves should be listed.

Then print m lines describing the columns of the Japanese crossword puzzle from left to right. Each of them should start with the number of numbers in that column, and then those numbers themselves should be listed.

For convenience, you can output additional newlines.

Examples

Input example #1
11 8
........
.####...
.######.
.##..##.
.##..##.
.######.
.####...
.##.....
.##.....
.##.....
........
Output example #1
0 
1 4 
1 6 
2 2 2 
2 2 2 
1 6 
1 4 
1 2 
1 2 
1 2 
0 

0 
1 9 
1 9 
2 2 2 
2 2 2 
1 4 
1 4 
0 

Source 2020 Cycle of Internet Olympiads for schoolchildren, Third team contest, Novemver 7, Problem D