题目描述

跛脚国王在一块 $n\times m$ 的棋盘上移动。每次移动时，他只能从当前格子走到与其有公共边的相邻格子。

用 $(x,y)$ 表示第 $x$ 行第 $y$ 列的格子。

跛脚国王需要访问棋盘上的所有格子，每个格子恰好访问一次，并最终回到起点。也就是说，需要构造一个经过所有格子的哈密顿回路。

此外，棋盘上给定了两个相邻的格子 $(x_1,y_1)$ 与 $(x_2,y_2)$。在国王的遍历顺序中，这两个格子必须连续出现：当国王到达其中一个格子后，下一步必须立刻走到另一个格子。

请输出一种满足条件的遍历顺序，或判断不存在这样的遍历。

输入格式

第一行输入两个整数 $n,m$，表示棋盘大小。

第二行输入四个整数 $x_1,y_1,x_2,y_2$，表示给定的两个相邻格子。

输出格式

如果不存在满足条件的遍历，输出：

-1

否则输出 $n\times m+1$ 对整数，表示国王按顺序经过的格子坐标。起点需要在开头和结尾各输出一次。

输出中的数可以用任意空白字符分隔。

数据范围

样例

样例 1 输入

4 3
2 2 3 2

样例 1 输出

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

样例 2 输入

3 5
1 2 2 2

样例 2 输出

-1

说明

第一个样例的路径示意图，图中灰色部分强调了给定的相邻格子在回路中连续经过。