DMOPC '21 Contest 8 P4 - Grid Operations

View as PDF

Submit solution


Points: 25 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

You have found a strange device that shows a 2N \times 2M grid of numbers. The rows are numbered from 1 to 2N, and the columns are numbered from 1 to 2M. Initially, the number at the intersection of the i-th row and the j-th column is equal to (i-1) \cdot 2M+j.

The grid is partitioned into an N \times M grid of 2 \times 2 subgrids. These subgrids are coloured white or black in a checkerboard pattern, with the top-left 2 \times 2 subgrid coloured white.

You notice that the device can perform 5 types of operations on the grid, which are:

  • Type 1: In every row, swap the numbers on each of the M adjacent pairs of cells with the same colour.
  • Type 2: In every row, swap the numbers on each of the M-1 adjacent pairs of cells with different colours.
  • Type 3: In every column, swap the numbers on each of the N adjacent pairs of cells with the same colour.
  • Type 4: In every column, swap the numbers on each of the N-1 adjacent pairs of cells with different colours.
  • Type 5: Rotate every white 2 \times 2 subgrid clockwise and rotate every black 2 \times 2 subgrid counterclockwise.

Now you wonder: What is the final state of the grid after performing Q operations of types t_1, t_2, \dots, t_Q in order?

Constraints

1 \le N, M, Q \le 10^6

1 \le N \times M \le 10^6

1 \le t_i \le 5

Subtask 1 [10%]

There are only type 1, 3, and 5 operations.

Subtask 2 [25%]

There are only type 1 and 2 operations.

Subtask 3 [10%]

There are only type 1, 2, 3, and 4 operations.

Subtask 4 [55%]

No additional constraints.

Input Specification

The first line contains 3 space-separated integers: N, M, and Q.

The next Q lines each contain an integer t_i, the type of an operation to perform.

Output Specification

Output 2N lines, each containing 2M space-separated integers: The final grid after performing all the operations.

Sample Input

2 3 5
3
1
4
2
5

Sample Output

20 8 12 24 21 9
22 10 7 19 23 11
4 16 13 1 5 17
2 14 18 6 3 15

Explanation

After the first operation, the grid looks like:

After the second operation, the grid looks like:

After the third operation, the grid looks like:

After the fourth operation, the grid looks like:

After the fifth operation, the grid looks like:


Comments

There are no comments at the moment.