P15128 [ROIR 2026] Lame King

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.

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$).

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.

### 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