시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 256 MB32266.667%

## 문제

The famous archaeologist Diana Jones has discovered a secret passageway leading to hidden treasure near Nowhere, Kansas. The passageway is blocked by a stone gate which has an ancient unlocking mechanism chiselled into it. Fortunately, she has immediately recognized the chiselled symbols:

1. The unlocking mechanism is a table with R rows and C columns. Each cell contains a unique positive integer between 1 and R*C, inclusive. At first glance, the numbers appear to be ordered randomly.
2. The mechanism contains cogwheels which Diana can use to rearrange the table cells. In one move, she can rotate any 2-by-2 group of adjacent cells clockwise by 90 degrees.
3. The gate will be unlocked when the numbers are rearranged in sorted row-major order (the upper left cell must contain 1, the cell to the right of it 2, and so on until the lower right cell, which must contain R*C).

For example, for the initial arrangement shown in the first picture, two moves are sufficient to unlock the mechanism:

Write a program that, given the initial arrangement of cells, finds a sequence of moves that unlocks the mechanism. The number of moves needn't be optimal, however it must not exceed 100 000.

## 입력

The first line of input contains the two positive integers R and C (2 ≤ R ≤ C ≤ 25).

Each of the following R lines contains C positive integers Zij (1 ≤ Zij ≤ R*C), the numbers chiselled into the corresponding mechanism cells, which describes the initial arrangement.

## 출력

The output must contain the required sequence of moves, one per line. For each move, output two positive integers M and N (1 ≤ M ≤ R-1, 1 ≤ N ≤ C-1) representing the row and column index of the upper left cell in the 2-by-2 group rotated in that move.

Note: For the given input data, a solution, not necessarily unique, will always exist.

## 예제 입력 1

2 3
3 2 6
1 4 5


## 예제 출력 1

1 1
1 2


## 예제 입력 2

3 3
1 2 3
4 6 9
7 5 8


## 예제 출력 2

2 2


## 예제 입력 3

2 4
1 2 7 3
5 6 8 4


## 예제 출력 3

1 3
1 3
1 3


## 힌트

Clarification of the first example: According to the picture in the problem description, the initial arrangement can be ordered in two moves: we first rotate the group with the upper left corner in row 1 and column 1, and then the group with the upper left corner in row 1 and column 2.