Description

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

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

Mirko’s favorite pastime is drawing a rectangular chessboard pattern using the command PAINT c x1 y1 x2 y2, where $c$ is the chosen color, and $(x1,y1)$ and $(x2,y2)$ are the top-left and bottom-right coordinates, respectively.

The top-left cell of the rectangle will be painted with the chosen color, and the rest will be colored like a chessboard. Cells not covered by the chosen color will keep their previous color.

For example, a white canvas painted with a red chessboard pattern looks like this:

Mirko recently discovered two more commands. He can save his drawing at any time using the SAVE command, and later load it again using the command load x, where $x$ is a positive integer representing the save index.

Unfortunately, the program crashed, and Mirko’s drawing was lost forever. Fortunately, Mirko has a log that contains all commands that were used. Can you help Mirko restore the lost drawing?

Input Format

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

Each of the next $M$ lines contains one of the three commands described above. The input will not contain any invalid commands.

Output Format

Output $N$ lines. Each line should contain $N$ integers representing the colors of the cells in that row of the final drawing.

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

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

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

3 1 1
1 3 1
1 1 1 

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 

2 1 1
1 3 1
4 1 3 

Hint

Sample Explanation #1

Command $1$ paints the cells from $(0,0)$ to $(3,3)$ in a chessboard pattern, meaning it paints $(0,0)$, $(0,2)$, $(1,1)$, $(1,3)$, $(2,0)$, $(2,2)$, $(3,1)$, $(3,3)$ with color $2$.

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

Constraints

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

Notes

The score of this problem follows the original COCI settings, with a full score of $130$.

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

Translated by ChatGPT 5