题目描述

跛脚国王在一个 $n \times m$ 的棋盘上移动，每次从当前格子移动到相邻的边相邻格子。我们用 $(x, y)$ 表示第 $x$ 行第 $y$ 列的格子。

跛脚国王必须访问所有格子，每个格子恰好经过一次，并回到起点。同时，棋盘上标出了两个相邻的格子：$(x_1, y_1)$ 和 $(x_2, y_2)$。在国王的棋盘遍历路径中，格子 $(x_1, y_1)$ 和 $(x_2, y_2)$ 必须连续出现：当国王到达其中一个格子后，必须立即移动到另一个格子。

请找出一个满足条件的棋盘遍历顺序，或者确定这样的顺序不存在。

输入格式

第一行包含两个整数 $n$ 和 $m$（$2 \le n, m \le 1000$）—— 棋盘的尺寸。

第二行包含四个整数 $x_1$, $y_1$, $x_2$, $y_2$ —— 两个相邻格子的坐标（$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$）。

输出格式

如果不存在这样的棋盘遍历路径，输出一个整数 $-1$。

否则，输出 $n \times m + 1$ 对整数 —— 按遍历顺序排列的格子坐标，起点格子需要在开头和结尾各输出一次。

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

提示

样例解释

图示展示了第一个样例的棋盘遍历路径。

:::align{center} :::

评分规则

本题共有 50 个测试点，每个测试点独立计分，分值为 2 分。

在本场比赛过程中，你会得知每个测试点的评测结果。

翻译由 DeepSeek 完成。