Problem Description

Mirko has just installed a new drawing program. The program supports $K$ different colors, represented by integers from $1$ to $K$. All drawings are done on a canvas of size $N \times N$. Initially, all cells are white (represented by 1).

The top-left cell of the canvas has coordinates $(0,0)$. The first coordinate $x$ represents the row, and the second coordinate $y$ represents the column.

Mirko's favorite pastime is using the PAINT c x1 y1 x2 y2 command to draw a rectangular checkerboard pattern, where $c$ is the selected color, and $(x1, y1)$ and $(x2, y2)$ are the coordinates of the top-left and bottom-right corners, respectively.

The top-left cell of the rectangle will be painted with the selected color, and the rest will be colored like a checkerboard. Cells not covered by the selected color will retain their previous colors.

For example, a white canvas painted with a red checkerboard pattern would look like this:

Mirko has recently discovered two additional commands. He can save his drawing at any time using the SAVE command and later reload it using the LOAD x command, where $x$ is a positive integer representing the save sequence number.

Unfortunately, the program crashed, and Mirko's drawing was lost forever. Fortunately, Mirko kept a log of all the commands used. Can you help Mirko restore the lost drawing?

Input Format

The first line of input contains three positive integers $N, K, M$, where $N$ is the side length of the canvas, $K$ is the number of colors, and $M$ is the number of commands.

The following $M$ lines each contain one of the three described commands. The input will not contain any illegal commands.

Output Format

The output consists of $N$ lines, each containing $N$ integers representing the color of the cells in that row.

Sample Input and Output

Sample Input #1

4 3 2
PAINT 2 0 0 3 3
PAINT 3 0 3 3 3

Sample Output #1

2 1 2 3
1 2 1 2
2 1 2 3
1 2 1 2

Sample Input #2

3 3 4
PAINT 3 0 0 1 1
SAVE
PAINT 2 1 1 2 2
LOAD 1

Sample Output #2

3 1 1
1 3 1
1 1 1

Sample Input #3

3 4 7
PAINT 2 0 0 1 1
SAVE
PAINT 3 1 1 2 2
SAVE
PAINT 4 0 2 0 2
LOAD 2
PAINT 4 2 0 2 0

Sample Output #3

2 1 1
1 3 1
4 1 3

Notes

[Sample Explanation #1]

Command 1 paints the cells from $(0,0)$ to $(3,3)$ in a checkerboard pattern, coloring $(0,0)$, $(0,2)$, $(1,1)$, $(1,3)$, $(2,0)$, $(2,2)$, $(3,1)$, and $(3,3)$ with color $2$.

Command 2 paints the cells from $(0,3)$ to $(3,3)$ in a checkerboard pattern, coloring $(0,3)$ and $(2,3)$ with color $3$.

[Data Range]

For $100\%$ of the data, $1 \le N \le 1000$, $2 \le K \le 10^5$, $1 \le M \le 10^5$.

[Notes]

This problem is scored according to the original COCI settings, with a maximum score of $130$.

The problem is translated from COCI2010-2011 CONTEST #5 T6 SLIKA.

见题面 Input 部分

见题面 Output 部分