Curling
A significant portion of the Olympic broadcasts from Vancouver focused on curling, which has since gained considerable popularity in Russia. In curling, players use granite stones to try to position them closer to the center of the target area, known as the house, than their opponents' stones. In official matches, all stones are of uniform size. However, during training, stones of varying diameters are used to help athletes refine different skills.
During these training sessions, equipment is used to capture overhead photographs of the stones' positions. This data is then analyzed to identify throwing errors. For better analysis, it's helpful to have all throws displayed on a single photograph by overlaying them. Your task is to create such a composite photograph based on the given information about the stones' positions on the ice.
The photograph is represented as a rectangle of size N*M cells. Each stone is depicted as a circle with its center at a specific cell and a radius defined as an integer number of cells. In the photograph, all cells (X, Y) within the i-th circle, where the center coordinates satisfy the inequality (X_0-X)^2 + (Y_0-Y)^2 ≤ R^2, are colored with the color C_i. Here, X_0 and Y_0 are the coordinates of the circle's center.
As you overlay the images of all stones sequentially, some cells may be painted multiple times; in such cases, the cell's color is determined by the last color applied. Some cells may remain unpainted.
Input
The first line contains the numbers N, M, K (3 ≤ N, M ≤ 2500, 1 ≤ K ≤ 5000). The following K lines provide details about the stones' positions on the playing field: X_i, Y_i, R_i, C_i. (0 ≤ X_i < N, 0 ≤ Y_i < M, 1 ≤ R < max(N,M)). The color is indicated by a single character, which is a letter from the Latin alphabet. Uppercase and lowercase letters are distinct.
Output
Output N rows of M characters, representing the photograph of all the stones. An unpainted cell should be marked with a dot. A painted cell should be marked with the character corresponding to its color.
An example of the output data is shown in the figure:
