Standing Pins

For a special presentation to the Computer Game Developers association, Mario built a two-dimensional histogram showing the number of game titles published, broken down by year and by game genre. On his spreadsheet it looked quite attractive.

Mario decided that a physical model would be even better, so he built one out of wire and cardboard (the left picture below). When it was packed for transport to the conference it looked like the right-hand picture below: every wire had been tipped down flat, either to the left or to the right at random, while its base stayed in the correct square.

Only when he unpacked the model did he realise there might be a problem. Whether each wire had been tipped left or right was never recorded. Worse, his assistant had not followed the packing instructions: not every wire was laid to the left or right — some were laid forward or backward on the card. The original data is gone. Your task is to write a program that works out how to stand the wires back up, and to keep it general in case this happens again.

Some inputs have a solution. For example, in the sketch on the right there are four pins, of lengths 1, 1, 3 and 2. They can only stand up with the two length-1 pins in column 1, and the length-2 and length-3 pins in column 2 (in rows 1 and 2 respectively).

Other inputs do not have a unique solution. For example, consider the second sketch: the three pins could be stood up with the length-2 pin either on the right or on the left. When more than one arrangement is possible in this way we cannot be sure which is correct, so we must report that there is no solution. Note, however, that there would have been no problem if the length-2 pin had been only 1 unit long: we might not know exactly which cell each pin came from, but we would be certain that every cell started with a pin of height 1, and that is fine.

The input contains several problems. Each problem begins with a line holding two integers $R$ and $C$, the number of rows and columns of the grid ($1 \le R, C \le 100$). This is followed by $R \times C$ lines, one per wire. Each such line holds the grid coordinates of the two ends of one wire as four integers $r_1; c_1; r_2; c_2$. One end lies in its correct grid cell (the base); the other end lies wherever the wire's length places it, because the wire was laid down either horizontally or vertically. The coordinates of that other end may fall outside the grid. Because a wire is straight, its two ends are exactly its length apart, and every length is an integer in the range $1$ to $9$ inclusive. The input ends with a line containing two zeros, which must not be processed.

Separate the answers of consecutive problems with a single blank line (there is no blank line before the first answer). If a problem's heights are not uniquely determined — either no valid arrangement exists, or two valid arrangements give different heights — print No solution. Otherwise print $R$ lines; the $i$-th line contains the $C$ single-digit heights of the wires standing in row $i$, written with no spaces between them.