A8188 | Petya and Rectangle

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<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<x_{1},x_{2}<n,1<y_{1},y_{2}<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.