D. X and paintings
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

X is well known artist, no one knows the secrete behind the beautiful paintings of X except his friend Y, well the reason that Y knows X's secrete is that he is that secret. Y is a programmer and he helps X with drawing paintings using computer program written by him. Unfortunately Y program is not working any more, now it's your turn to help X by writing a program that helps him in painting, your program should accept a sequence of instructions, each will draw an opaque (filled) rectangle in the form: r1, c1, r2, c2, color. where (r1, c1) is the upper left corner of the rectangle and (r2, c2) is the lower right corner, and color is a character that denotes the color of this rectangle. all rectangles will be printed on a R by C plane, by default this plane is filled with dots (i.e. '.'). R and C between 1 and 100. for each instruction (1 ≤ ri ≤ R) and (1 ≤ ci ≤ C) and color is a ASCII character [a-z]. The number of instructions won't exceed 100 instructions.

Input

The first line of input contains an integer T denotes number of test cases. The first line of each test case contains three integers R, C ,I where R and C denotes number of rows and columns of the painting, and I denotes number of instructions. Each of the next I lines contains four integers r1,c1,r2,c2 and the color character.

Output

Print the final plane after evaluating the instructions in order.

Example
Input
1
5 5 3
1 1 2 2 a
1 2 5 5 c
2 2 3 3 d
Output
acccc
addcc
.ddcc
.cccc
.cccc