8*8 的国际象棋棋盘上的一只马，恰好走过除起点外的其它 63 个位置各一次，最后回

到起点。这条路线称为一条马的 Hamilton 周游路线。对于给定的 m*n 的国际象棋棋盘，m

和n均为大于5的偶数，且|m-n|≤2，试设计一个分治算法找出一条马的Hamilton周游路线。



编程任务：

对于给定的偶数m，n≥6，且|m-n|≤2，编程计算 m*n 的国际象棋棋盘一条马的Hamilton

周游路线。



Input



输入数据的第一行有2个正整数m和 n，表示给定的国际象棋棋盘

由 m行，每行n个格子组成。



Output



将计算出的马的Hamilton周游路线用下面的2 种表达方式输出。

第 1 种表达方式按照马步的次序给出马的 Hamilton 周游路线。马的每一步用所在的方

格坐标(x，y)来表示。x表示行的坐标，编号为 0，1，…，m-1；y表示列的坐标，编号为 0，

1，…，n-1。起始方格为（0，0）。

第 2 种表达方式在棋盘的方格中标明马到达该方格的步数。（0，0）方格为起跳步，并

标明为第1步。

-8* 8 chess board on a horse, just walk outside than from the other 63 positions each time, and finally back

To the starting point. This line is called Hamilton a horse travel routes. For a given m* n chess board, m

And n are even greater than 5, and | mn | ≤ 2, the partition algorithm to design a test to find a horse of Hamilton travel routes.



Programming tasks:

For a given even number m, n ≥ 6, and | mn | ≤ 2, programming computing m* n chess board a horse Hamilton

Travel routes.



Input



The first line of input data are two positive integers m and n, that a given chessboard

By the m lines of n-grid component.



Output



The calculated travel route horse Hamilton 2 with the following expression of the output.

The first one kind of expression is given in accordance with the order of the horse Horse Hamilton travel routes. Horse with each step of the square where

Grid coordinates (x, y) to represent. the coordinates of x that line, numbered 0,1, ..., m-1　y co