Parade

Time limit1sMemory limit128 MB

Summary

Maintain a list of N perimeter-rotation commands on a 4x4 grid under Q cumulative point updates, printing the resulting grid after each update.

Level: Medium7 of 10
Topics: Simulation, Implementation, Array, Prefix sum
Solved: No attempts yet

Problem

May 9 is Victory Day, when an annual victory parade marches through Red Square. To rehearse it digitally, you must track how a single formation changes.

A formation is a $4 \times 4$ grid. The people start labelled $1$ through $16$ in row-major order:

1  2  3  4
5  6  7  8
9  10 11 12
13 14 15 16

A sequence of commands is then issued. Each command is a triple $(r, c, k)$ meaning:

Rotate every person on the perimeter of the $k \times k$ square whose upper-left corner is at row $r$ , column $c$ clockwise by one position.

For example, command $(1, 1, 2)$ turns the initial grid into:

5 1 3 4
6 2 7 8
9 10 11 12
13 14 15 16

Command $(2, 2, 3)$ turns the initial grid into:

1 2 3 4
5 10 6 7
9 14 11 8
13 15 16 12

Command $(1, 1, 4)$ turns the initial grid into:

5 1 2 3
9 6 7 4
13 10 11 8
14 15 16 12

You are given the original sequence of $N$ commands. You then perform $Q$ edits. Each edit permanently rewrites one command:

Change the $i$ -th command to $(r', c', k')$ .

Every edit is cumulative and permanent: it modifies the same command list that previous edits already changed. After each edit, output what the formation looks like once all $N$ commands (with every edit applied so far) have been executed in order on the initial grid.

Input

The first line contains two integers $N$ and $Q$ ( $1 \le N, Q \le 100000$ ) — the number of commands and the number of edits.

Each of the next $N$ lines contains three integers $r$ , $c$ , $k$ describing one rotation command, with $1 \le k \le 4$ , $r + k - 1 \le 4$ , and $c + k - 1 \le 4$ .

Each of the next $Q$ lines contains four integers $i$ , $r'$ , $c'$ , $k'$ : the $1$ -based index $i$ of the command to rewrite, followed by its new description $(r', c', k')$ (subject to the same bounds on $r'$ , $c'$ , $k'$ ).

Output

For each edit, print the final $4 \times 4$ configuration after applying every edit so far, as $4$ lines of $4$ space-separated integers. Print the blocks for the $Q$ edits one after another, with no blank lines between them.

Notes

Each edit changes the command list in place, and the changes accumulate: the $j$ -th edit is applied on top of edits $1 \ldots j-1$ .
A command with $k = 1$ acts on a single cell and therefore leaves the formation unchanged.
The answer after each edit is uniquely determined, so the required output is exact.

Examples2

Example 1

Input

Expected output

5 1 3 4
6 2 7 8
9 10 11 12
13 14 15 16
5 1 3 4
6 10 2 7
9 14 11 8
13 15 16 12
1 2 3 4
5 10 6 7
9 14 11 8
13 15 16 12
5 1 2 3
9 6 7 4
13 10 11 8
14 15 16 12

Example 2

Input

Expected output

6 5 1 4
9 2 3 8
10 11 15 7
13 14 16 12
5 1 2 4
9 6 3 8
10 11 15 7
13 14 16 12