Donggyu's Keyboard Paint Program

Donggyu installed a new paint program. The program supports K colors numbered from 1 to K, and it draws on an N×N canvas. Initially every cell has color 1.

The coordinate of the top-left cell is (0, 0). In a coordinate (x, y), x is the row and y is the column.

The main command is PAINT c x1 y1 x2 y2. It paints the rectangle whose top-left coordinate is (x1, y1) and whose bottom-right coordinate is (x2, y2) in a checkerboard pattern. Inside that rectangle, only cells whose (x + y) parity is the same as (x1 + y1) change to color c. The other cells are not painted and keep their current colors. Therefore, the top-left cell of the rectangle always becomes color c.

There are two more commands. SAVE stores the current canvas. Saved canvases are numbered from 1 in the order the SAVE commands are executed. LOAD x restores the x-th saved canvas and makes it the current canvas.

The program recorded every command in order. After executing all commands, determine the color of every cell in the final canvas.

The first line contains N, K, and M.

• 1 ≤ N ≤ 1000
• 2 ≤ K ≤ 100000
• 1 ≤ M ≤ 100000

M is the number of commands. Each of the next M lines contains one command: PAINT c x1 y1 x2 y2, SAVE, or LOAD x. No invalid command is given.

Print N lines describing the final canvas. Each line must contain N color numbers for that row, separated by spaces.