You have found a strange device that shows a grid of numbers. The rows are numbered from
to
, and the columns are numbered from
to
. Initially, the number at the intersection of the
-th row and the
-th column is equal to
.
The grid is partitioned into an grid of
subgrids. These subgrids are coloured white or black in a checkerboard pattern, with the top-left
subgrid coloured white.
You notice that the device can perform types of operations on the grid, which are:
- Type
1
: In every row, swap the numbers on each of theadjacent pairs of cells with the same colour.
- Type
2
: In every row, swap the numbers on each of theadjacent pairs of cells with different colours.
- Type
3
: In every column, swap the numbers on each of theadjacent pairs of cells with the same colour.
- Type
4
: In every column, swap the numbers on each of theadjacent pairs of cells with different colours.
- Type
5
: Rotate every whitesubgrid clockwise and rotate every black
subgrid counterclockwise.
Now you wonder: What is the final state of the grid after performing operations of types
in order?
Constraints
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 space-separated integers:
,
, and
.
The next lines each contain an integer
, the type of an operation to perform.
Output Specification
Output lines, each containing
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