Petya and Rectangle

题意翻译

### 题目描述 给出一个矩阵，矩阵被等分成 $n\times m$ 个格子（$n$ 行 $m$ 列，$4\le n,m\le1000$），给出两个格子坐标 $(x_1,y_1)$ $(x_2,y_2)$，分别为起点终点，求从一点到另一点的最长路径长度和此路径所经过的格子坐标。 ### 输入格式 共三行 第一行两个数 $n$ 和 $m$，表示矩阵大小 第二行为起点坐标 $(x_1,y_1)$ 第三行为终点坐标 $(x_2,y_2)$ ### 输出格式 第一行为最长路径长度 此后若干行，每行两个数，表示路径经过的格子坐标，包括起点终点，并从起点开始到终点顺次输出 如果有多条路径满足情况，输出其中一条即可

题目描述

Little Petya loves playing with rectangles. Mom bought Petya a rectangle divided into cells $ n×m $ in size (containing $ n $ rows, $ m $ columns). Petya marked two different cells of the rectangle and now he is solving the following task: Let's define a simple path between those two cells as a sequence of distinct cells $ a_{1},a_{2},...,a_{k} $ , where $ a_{1} $ and $ a_{k} $ are the two marked cells. Besides, $ a_{i} $ and $ a_{i+1} $ are side-neighboring cells of the path ( $ 1<=i&lt;k $ ). Let's denote the path length as number $ k $ (the sequence length). Petya's task is to find the longest simple path's length and to print the path. Help him.

输入输出格式

输入格式

The first line contains space-separated integers $ n $ and $ m $ ( $ 4<=n,m<=1000 $ ) — the number of rows and the number of columns in the rectangle, correspondingly. The second line contains space-separated integers $ x_{1} $ and $ y_{1} $ — the coordinates of the first marked cell. The third line contains space-separated integers $ x_{2} $ $ y_{2} $ — the coordinates of the second marked cell ( $ 1&lt;x_{1},x_{2}&lt;n,1&lt;y_{1},y_{2}&lt;m,x_{1}≠x_{2},y_{1}≠y_{2} $ ). The coordinates of a marked cell are a pair of integers $ x $ $ y $ , where $ x $ represents the row's number and $ y $ represents the column's number. The rows are numbered from top to bottom with consecutive integers from $ 1 $ to $ n $ . The columns are numbered from the left to the right by consecutive integers from $ 1 $ to $ m $ . It is guaranteed that the marked cells are not positioned in one row or column.

输出格式

In the first line print the length of the found path — $ k $ . In the next lines print $ k $ pairs of integers, one per line — coordinates of the cells that constitute the found path in the order, in which they follow in the path (the path must go from cell $ (x_{1},y_{1}) $ to cell $ (x_{2},y_{2}) $ ). If there are several solutions, print any of them.

输入输出样例

输入样例 #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

说明

The statement test is described in the picture: