Recover the Lost Drawing

Mirko has just installed a new drawing program that supports (K) different colors, represented by the integers from (1) to (K). All drawings are made on an (N \times N) canvas. Initially, every cell of the canvas is white (represented by the integer (1)). The cell at the top‐left corner is at coordinate ((0,0)) where the first coordinate (x) indicates the row and the second coordinate (y) indicates the column.


Mirko loves to use the PAINT c x1 y1 x2 y2 command to draw a rectangular checkerboard pattern. In this command, (c) is the chosen color, and ((x1,y1)) and ((x2,y2)) are the coordinates of the top‐left and bottom‐right corners of the rectangle, respectively. The top‐left cell of the rectangle is painted with the chosen color (c) and the pattern follows like a chessboard, i.e. a cell ((i,j)) in the rectangle is painted with (c) if and only if ((i - x1 + j - y1) \bmod 2 = 0). Cells in the rectangle that are not updated (when the condition fails) retain their previous color.


In addition, Mirko discovered two more commands: SAVE and load x. When he issues the command SAVE, the current state of the canvas is saved with a sequence number (starting from 1 for the first save). Later, the command load x can be used to revert to the state of the canvas that was saved with sequence number (x).

Unfortunately, the program crashed and Mirko's drawing was lost. Luckily, Mirko kept a log of all the commands he used. Can you help him recover the lost drawing?

inputFormat

The first line of the input contains three integers (N), (K), and (Q), where (N) is the size of the canvas, (K) is the number of available colors, and (Q) is the number of commands in the log. Each of the following (Q) lines contains one command. A command is one of the following three types:

1. PAINT c x1 y1 x2 y2 — Paint the rectangular region from ((x1,y1)) to ((x2,y2)) (inclusive) with a checkerboard pattern using color (c). Only those cells ((i,j)) for which ((i-x1+j-y1) \bmod 2 = 0) will be updated to color (c).
   
2. SAVE — Save the current state of the canvas. The saves are numbered sequentially starting from 1.
   
3. load x — Revert the canvas to the state saved with sequence number (x).
   
   Note that the canvas is initially filled with (1) (white).

outputFormat

Output the final state of the canvas after processing all (Q) commands. Print (N) lines, each containing (N) space-separated integers representing the colors of the cells.

sample

3 5 1
PAINT 3 0 0 2 2

3 1 3
1 3 1
3 1 3