회전 횟수의 홀짝

고고학자 다이애나 존스가 캔자스주 노웨어 근처에서 숨겨진 보물로 이어지는 비밀 통로를 찾아냈다. 통로는 돌문이 막고 있고, 문에는 고대의 잠금 해제 장치가 새겨져 있다. 다이애나는 새겨진 기호를 보자마자 알아봤다.

1. 잠금 해제 장치는 $R$행 $C$열짜리 표다. 각 칸에는 $1$ 이상 $R \times C$ 이하의 정수가 하나씩 적혀 있고, 같은 수는 두 번 나오지 않는다. 언뜻 보면 수가 아무렇게나 놓인 것 같다.
2. 장치에는 톱니바퀴가 달려 있어서 칸의 배치를 바꿀 수 있다. 한 번의 이동으로 서로 인접한 $2 \times 2$ 칸을 시계 방향으로 $90$도 회전한다.
3. 수가 행 우선 순서로 정렬되면 문이 열린다. 왼쪽 위 칸에 $1$, 그 오른쪽 칸에 $2$가 오는 식으로 이어져서 오른쪽 아래 칸에 $R \times C$가 놓여야 한다.

아래 그림의 배치는 이동 두 번으로 문이 열린다.

다이애나에게 필요한 것은 이동 순서 자체가 아니라 이동 횟수의 홀짝이다. 한 배치를 정렬하는 이동 순서는 여러 가지지만, 그 길이의 홀짝은 모두 같다. 처음 배치가 주어졌을 때 이동 횟수가 짝수인지 홀수인지 구하는 프로그램을 작성하시오.

첫째 줄에 정수 $R$과 $C$가 주어진다 ($2 \le R \le C \le 25$).

다음 $R$개의 줄에는 각 줄마다 정수 $Z_{ij}$가 $C$개씩 주어진다 ($1 \le Z_{ij} \le R \times C$). 이 수는 장치의 각 칸에 새겨진 값이고, 처음 배치를 나타낸다. 모든 값은 서로 다르다.

주어진 배치는 항상 문을 열 수 있다.

이동 횟수가 짝수이면 $0$, 홀수이면 $1$을 한 줄에 출력한다.

그림의 배치는 왼쪽 위 모서리가 1행 1열인 $2 \times 2$ 칸을 먼저 회전하고, 이어서 왼쪽 위 모서리가 1행 2열인 $2 \times 2$ 칸을 회전하면 정렬된다. 이동을 두 번 했으므로 답은 $0$이다.