Parade

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.

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'$).

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.

• 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.