Under construction

Still being built. Things may change

Donggyu's Keyboard Paint Program

Time limit2sMemory limit128 MB

Summary
Simulate up to 100000 paint, save, and load commands on an N by N grid with checkerboard rectangle fills and version rollback, then output the final grid.
Level

Medium7 of 10

Topics
Simulation, Implementation, Matrix
Solved
No attempts yet

Problem

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.

Input

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.

Output

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

Examples3

  1. Example 1

    Input
    4 3 2
PAINT 2 0 0 3 3
PAINT 3 0 3 3 3
    Expected output
    2 1 2 3
1 2 1 2
2 1 2 3
1 2 1 2

  2. Example 2

    Input
    3 3 4
PAINT 3 0 0 1 1
SAVE
PAINT 2 1 1 2 2
LOAD 1
    Expected output
    3 1 1
1 3 1
1 1 1

  3. Example 3

    Input
    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
    Expected output
    2 1 1
1 3 1
4 1 3