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: