小 Petya 喜欢玩矩形。妈妈给 Petya 买了一个矩形,分为 n × m 大小的单元格(包含 n 行,m 列)。 Petya 标记了矩形的两个不同单元格,现在他正在解决以下任务:
让我们将这两个单元之间的简单路径定义为不同单元 a1、a2、...、ak 的序列,其中 a1 和 ak 是两个标记的单元。此外,ai 和ai + 1 是路径的旁边相邻单元(1 ≤ i < k)。我们将路径长度表示为数字 k(序列长度)。
Petya 的任务是找到最长的简单路径的长度并打印该路径。帮助他。
输入
第一行包含空格分隔的整数 n 和 m (4 ≤ n, m ≤ 1000) — 相应地,矩形中的行数和列数。第二行包含空格分隔的整数 x1 和 y1 — 第一个标记单元的坐标。第三行包含空格分隔的整数 x2 y2 — 第二个标记单元的坐标 (1 < x1, x2 < n, 1 < y1, y2 < m, x1 ≠ x2, y1 ≠ y2)。
标记单元格的坐标是一对整数 x y,其中 x 表示行号,y 表示列号。行从上到下使用从 1 到 n 的连续整数进行编号。这些列从左到右用 1 到 m 的连续整数进行编号。
保证标记的单元格不位于一行或一列中。
输出
在第一行中打印找到的路径的长度 — k。在接下来的行中,打印 k 对整数,每行一个 - 构成所找到路径的单元格的坐标,按顺序排列,它们在路径中遵循这些顺序(路径必须从单元格 (x1, y1) 到单元格 (x2, y2))。如果有多个解决方案,请打印其中任何一个。
示例
输入 #1
4 4 2 2 3 3
输出 #1
15 2 2 1 2 1 1 2 1 3 1 4 1 4 2 4 3 4 4 3 4 2 4 1 4 1 3 2 3 3 3
注意
语句测试如图所示: