Rotation Parity

The archaeologist Diana Jones has found a secret passage to hidden treasure near Nowhere, Kansas. A stone gate blocks the passage, and an ancient unlocking mechanism is chiselled into the gate. Diana recognized the chiselled symbols at once.

1. The mechanism is a table with $R$ rows and $C$ columns. Each cell holds one integer between $1$ and $R \times C$, and no value appears twice. At first glance the numbers look randomly placed.
2. The mechanism has cogwheels that rearrange the cells. In one move Diana rotates a $2 \times 2$ group of adjacent cells clockwise by $90$ degrees.
3. The gate opens when the numbers are sorted in row-major order. The upper left cell must hold $1$, the cell to its right $2$, and so on until the lower right cell, which must hold $R \times C$.

The arrangement in the picture below is unlocked by two moves.

Diana does not need the moves themselves, only whether their number is even or odd. One arrangement admits many unlocking sequences, and all of them have the same length parity. Given the initial arrangement, write a program that decides whether the number of moves is even or odd.

The first line contains the integers $R$ and $C$ ($2 \le R \le C \le 25$).

Each of the next $R$ lines contains $C$ integers $Z_{ij}$ ($1 \le Z_{ij} \le R \times C$), the values chiselled into the cells of the initial arrangement. All values are different.

The given arrangement can always be unlocked.

Print $0$ if the number of moves is even and $1$ if it is odd.

The arrangement in the picture is sorted by first rotating the group whose upper left corner sits in row 1 and column 1, then the group whose upper left corner sits in row 1 and column 2. That is two moves, so the answer is $0$.