Problem Description

The Lame King moves on an $n \times m$ chessboard. Each move goes from the current cell to an edge-adjacent cell. We use $(x, y)$ to denote the cell in row $x$ and column $y$.

The Lame King must visit all cells, passing through each cell exactly once, and return to the starting cell. Meanwhile, two edge-adjacent cells are marked on the board: $(x_1, y_1)$ and $(x_2, y_2)$. In the king’s traversal path, the cells $(x_1, y_1)$ and $(x_2, y_2)$ must appear consecutively: after the king reaches one of them, it must immediately move to the other.

Find a traversal order that satisfies the conditions, or determine that no such order exists.

Input Format

The first line contains two integers $n$ and $m$ ($2 \le n, m \le 1000$), the size of the board.

The second line contains four integers $x_1$, $y_1$, $x_2$, $y_2$, the coordinates of two edge-adjacent cells ($1 \le x_1, x_2 \le n$; $1 \le y_1, y_2 \le m$; $|x_1-x_2|+|y_1-y_2|=1$).

Output Format

If no such traversal path exists, output a single integer $-1$.

Otherwise, output $n \times m + 1$ pairs of integers, the cell coordinates in traversal order. The starting cell should be output once at the beginning and once at the end.

4 3
2 2 3 2

1 1
2 1
2 2
3 2
3 1
4 1
4 2
4 3
3 3
2 3
1 3
1 2
1 1

3 5
1 2 2 2

-1

Hint

Sample Explanation

The diagram shows the traversal path for the first sample.

:::align{center} :::

Scoring Rules

This problem has 50 test points. Each test point is scored independently and is worth 2 points.

During the contest, you will be able to see the judging result for each test point.

Translation completed by DeepSeek.

Translated by ChatGPT 5