Description

Graphics libraries usually implement drawing of graphics primitives, like lines, polygons and circles. Your task is to write a program that draws circles.

Graphic canvas is represented as an array of X_size

by Y

_size

pixels. Each pixel have a color ranged from 0 to 9. Initially all pixels have color 0. Pixels are thought of as small sqares with the side of length 1. A circle with center (xc, yc) and radius R is a set of pixels (x, y) satisfying the inequality (x − xc)

²

+ (y − yc)

²

≤ R

²

To draw a circle, your program should set the color of all pixels in a set defined above to the color of the circle. After drawing N given circles, the program should output the color of all pixels of the canvas.

Input

Input contains numbers X

_size

Y

_size

N followed by N sets of numbers xi yi Ri ci, describing the coordinates of center, radius and color of i-th circle.

1 <= X_size

, Y

_size

<= 1000, 1 <= N <= 10000, 0 <= xi < X

_size

, 0 <= yi < Y

_size

, 1 <= Ri <= 212, 0 <= ci <= 9.

Output

Output should contain Y

_size

lines of X

_size

characters each, where i-th character of j-th line is a digit corresponding to color of the pixel (i, j).

5 5 1
2 2 1 3

00000
00300
03330
00300
00000

Hint

This problem has huge input and output data,use scanf() and printf() instead of cin and cout to read data to avoid time limit exceed.

Source

Northeastern Europe 2004

, Far-Eastern Subregion