E. Петя и прямоугольник
ограничение по времени на тест
5 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Маленький Петя любит играть с прямоугольниками. Мама подарила Пете клетчатый прямоугольник размера n × m (n строк, m столбцов). Петя отметил две различные клетки прямоугольника и теперь решает следующую задачу.

Будем называть простым путем между этими клетками последовательность различных клеток a1, a2, ..., ak, где a1 и ak — две отмеченные клетки, при этом ai и ai + 1 являются соседними по стороне клетками пути (1 ≤ i < k). Длиной пути будем называть число k (длину последовательности).

Задача Пети — найти длину самого длинного простого пути, а также вывести сам путь. Помогите ему.

Входные данные

В первой строке через пробел записаны целые числа 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 строках выведите k пар чисел, по одной паре в строке — координаты клеток, входящих в найденный путь в порядке следования в пути (путь должен следовать из клетки (x1, y1) в клетку (x2, y2)). Если решений несколько, выведите любое.

Примеры
Входные данные
4 4
2 2
3 3
Выходные данные
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
Примечание

Рисунок, описывающий тест из условия: