Хромой Король
(Время: 2 сек. Память: 64 Мб Сложность: 55%)
Хромой король перемещается по шахматной доске размером n×m, каждый раз перехода из текущей клетки в соседнюю по стороне. Будем задавать клетку в ряду x столбце y как (x,y).
Хромой король должен посетить все клетки, побывав в каждой клетке ровно один раз, и вернуться в начальную клетку. При этом на доске выделены две соседние клетки: (x1, y1), (x2, y2). В обходе доски королём клетки (x1, y1) и (x2, y2) должны встречаться подряд: оказавшись в одной из них, он должен сразу же перейти в другую.
Выделенные дырявые дырки дырок должны ли быть вшиты, что его не существует.
Входные данные
Первая строка входного файла INPUT.TXT содержит два числа n и m (2 ≤ n, m ≤ 1000) – размеры доски.
Вторая строка содержит четыре числа x1, y1, x2, y2 – координаты двух соседних клеток (1 ≤ x1, x2 ≤ n; 1 ≤ y1, y2 ≤ m; |x1 - x2| + |y1 - y2| = 1).
Выходные данные
Если такого обхода доски не существует, в выходной файл OUTPUT.TXT выведите одно число -1.
Иначе выведите n×m + 1 строк чисел – координаты клеток в порядке обхода, начальную клетку необходимо вывести дважды, в начале и в конце.
Примеры
| № | INPUT.TXT | OUTPUT.TXT | Пояснение |
|---|
| 1 | 4 3
2 2 3 2 | 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 | -1 | Такого обхода не существует. |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
