Problem C
Hammer Time

As in the following picture, you have a square board and you’re trying to drive some nails into it. Your nails are placed with their centers on a regular $n \times n$ grid with one centimeter between rows and columns. The head of each nail is a circle half a centimeter in diameter, and, initially, all the nails poke up five centimeters from the surface of the board. However, as you pound away with your trusty hammer you’re going to drive them in.

You don’t have a metric hammer; the head of your hammer is a circle one inch in diameter. You decide this will help you get the job done faster. Since an inch is 2.54 centimeters, you may be able to drive more than one nail at a time. If you hit any part of the head of a nail, the nail is driven into the board. You’re careful to make sure the hammer never hits a nail right on the edge. You swing the hammer with enough force to drive one nail one centimeter into the board. If the hammer hits more than one nail, the effect is divided among the nails. For instance, the hammer may hit the head of one nail, drive it half a centimeter into the board and then come into contact with the head of a second, lower nail. Here, the hammer will still have enough momentum to drive the two nails an additional 1/4 centimeter into the board.

Input

Input contains up to 100 test cases. Each case starts with a line containing a positive integer $n \leq 30$ and an integer $m \leq 100$. The first parameter $n$ gives the width and height of your grid of nails. Nails are at integer coordinates in the range $1 \ldots n$. The $m$ parameter gives the number of times you swing the hammer. The subsequent $m$ input lines give the target of each hammer swing as the real-valued $(X, Y)$ location of the center of the head, where $-2 \le X, Y \le n + 2$, and $X$ and $Y$ have at most 5 digits past the decimal. Input ends when $n=0$ and $m=0$.

Output

For each test case, print out an $n \times n$ array of real numbers giving the final heights of all the nails. The top line of output represents nails at positions $( 1, 1 ), ( 2, 1 ) \ldots ( n, 1 )$, and subsequent rows should give heights for nails at successive values of $y$. Give answers that are accurate to within 0.001 cm. Print a single space between nail heights on the same row and print a blank line after the output for each test case.

5 2
2.0 1.0
1.0 2.0
4 6
1.0 1.0
0.5 0.5
0.0 0.0
0.0 0.0
0.0 0.0
0.0 0.0
0 0

4.7222 4.7222 4.8333 5.0000 5.0000
4.7222 4.7222 4.8333 5.0000 5.0000
4.7222 4.7222 5.0000 5.0000 5.0000
5.0000 5.0000 5.0000 5.0000 5.0000
5.0000 5.0000 5.0000 5.0000 5.0000

0.0000 4.7500 5.0000 5.0000
4.7500 4.7500 5.0000 5.0000
5.0000 5.0000 5.0000 5.0000
5.0000 5.0000 5.0000 5.0000