2009 Canadian Computing Competition, Stage 2

Day 2, Problem 2: Parade

May 9 is VE day, when the annual victory parade is held through Red Square. Inspired by the award ceremony of the 2009 ACM World Finals, you have decided to recreate the original VE day parade digitally. Since you have skillfully obtained all the necessary hardware, the most difficult part remaining is to track the configuration of a single formation.

A formation can be viewed as a 4-by-4 array, with the people initially labelled 1 through 16:

Then a sequence of commands (r, c, k) are issued. Each command is a rotation based on the three integer parameters r, c and k:

Rotate all people on the perimeter of a k-by-k square with its upper left corner located at row r, column c clockwise by one position.

For example, the command (1, 1, 2) would alter the initial board to:

As another example, (2, 2, 3) would bring the initial board to

A third example, (1, 1, 4) would bring the initial board to

You have obtained the original sequence of commands issued. However, you are not quite pleased with the final result and would like to edit some of the commands. Support Q (1 ≤ Q ≤ 100, 000) changes of the command sequence, each change as follows:

Change the ith command to r', c', and k' permanently.

Furthermore, you would like to see the effects of your change immediately. After each change, output what the formation would looks like at the end of all N commands. To re-emphasize, each change is cumulative and permanent.

For 30% of the test cases, 1 ≤ N, Q ≤ 1000.

Input

The first line contains two integers N and Q (1 ≤ N, Q ≤ 100,000), which is the number of commands and number of edits, respectively.

The next N lines contain three integers per line: r c and k which describe each rotation command. Note that 1 ≤ k ≤ 4, r + k - 1 ≤ 4 and c + k - 1 ≤ 4.

The next Q lines contain four integers per line: the first integer on the line is the 1-based index of the command whose detail is to be changed, followed by 3 integers, r', c', k', the new description of the command.

Output

For each change, print 4 lines, the final configuration of the formation after the modifications so far.

Sample Input

2 4
1 1 1
1 1 1
1 1 1 2
2 2 2 3
1 1 1 1
2 1 1 4

Sample 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

Explanation

The two commands (1, 1, 1) leave the configuration unchanged. The first change (1, 1, 2) on the initial configuration causes the configuration to become the first configuration in this problem statement. That is,

The second change takes this configuration and applies (2, 2, 3).

The next change alters the first change to be the original command, and then, since the second command has been changed to (2, 2, 3), we have

The last change causes the second command to be (1, 1, 4) which rotates the outermost perimeter of the previous output.

All Submissions
Best Solutions

Point Value: 30 (partial)
Time Limit: 1.00s
Memory Limit: 128M
Added: Jun 06, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)