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 the adjacent pairs of cells with the same colour. - Type
`2`

: In every row, swap the numbers on each of the adjacent pairs of cells with different colours. - Type
`3`

: In every column, swap the numbers on each of the adjacent pairs of cells with the same colour. - Type
`4`

: In every column, swap the numbers on each of the adjacent pairs of cells with different colours. - Type
`5`

: Rotate every white subgrid 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