Nhà khảo cổ học nổi tiếng Diana Jones đã phát hiện ra một lối đi bí mật dẫn đến kho báu được cất giấu gần Nowhere, Kansas. Lối đi bị chặn bởi một cánh cổng đá có cơ chế mở khóa cổ xưa được khắc vào đó. May mắn thay, cô đã nhận ra ngay những biểu tượng được chạm khắc:

1. Cơ chế mở khóa là một bảng có ~R~ hàng và cột ~C~. Mỗi ô chứa một số nguyên dương duy nhất nằm trong khoảng từ ~1~ đến ~R*C~. Thoạt nhìn, các con số dường như được sắp xếp ngẫu nhiên.
2. Cơ chế này chứa các bánh răng mà Diana có thể sử dụng để sắp xếp lại các ô trong bảng. Trong một lần di chuyển, cô ấy có thể xoay bất kỳ nhóm ~2 \times 2~ ô liền kề nào theo chiều kim đồng hồ 90 độ.
3. Cổng sẽ được mở khóa khi các số được sắp xếp lại theo thứ tự hàng lớn được sắp xếp (ô phía trên bên trái phải chứa ~1~, ô bên phải là ~2~, v.v. cho đến ô phía dưới bên phải, ô này phải chứa ~R*C~).

Ví dụ: đối với cách sắp xếp ban đầu được hiển thị trong hình ảnh đầu tiên, hai bước di chuyển là đủ để mở khóa cơ chế:

Viết một chương trình, với cách sắp xếp ban đầu của các ô, tìm một chuỗi các bước di chuyển để mở khóa cơ chế. Số lần di chuyển không cần phải tối ưu nhưng không được vượt quá ~100 000~.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~R~ và ~C~ ~(2 \le R \le C \le 25)~.
• Mỗi dòng trong số ~R~ dòng tiếp theo chứa ~C~ số nguyên dương ~Z_{ij}~ ~(1 ≤ Z_{ij} ≤ R*C)~, các số được khắc vào các ô cơ chế tương ứng, mô tả sự sắp xếp ban đầu.

Output

• Đầu ra phải chứa chuỗi các bước di chuyển được yêu cầu, mỗi bước một dòng. Đối với mỗi lần di chuyển, xuất ra hai số nguyên dương ~M~ và ~N~ ~(1 \le M \le R-1, 1 \le N \le C-1)~ biểu thị chỉ số hàng và cột của ô phía trên bên trái trong nhóm ~2 \times 2~ được xoay trong lần di chuyển đó .
• Lưu ý: Đối với dữ liệu đầu vào đã cho, sẽ luôn tồn tại một giải pháp, không nhất thiết là duy nhất.

Scoring

• Trong dữ liệu thử nghiệm có tổng giá trị là 40 điểm, ~R*C~ sẽ có nhiều nhất là ~9~.
• Trong dữ liệu thử nghiệm có tổng điểm là 40 điểm, ~R~ sẽ bằng ~2~.
• Trong dữ liệu thử nghiệm có tổng giá trị là 60 điểm, ít nhất một trong hai ràng buộc trên sẽ được giữ nguyên.

Sample Input 1

2 3
3 2 6
1 4 5

Sample Output 1

1 1
1 2

Sample Input 2

3 3
1 2 3
4 6 9
7 5 8

Sample Output 2

2 2

Sample Input 3

2 4
1 2 7 3
5 6 8 4

Sample Output 3

1 3
1 3
1 3

Làm rõ ví dụ đầu tiên:

• Theo hình ảnh mô tả bài toán, sự sắp xếp ban đầu có thể được sắp xếp theo hai bước: đầu tiên chúng ta xoay nhóm có góc trên bên trái ở hàng ~1~ và cột ~1~, sau đó là nhóm có góc trên bên trái góc ở hàng ~1~ và cột ~2~.