Хромой король перемещается по клетчатой доске размером $$$n \times m$$$, каждый раз переходя из текущей клетки в соседнюю по стороне. Будем задавать клетку в ряду $$$x$$$ столбце $$$y$$$ как $$$(x, y)$$$.
Хромой король должен посетить все клетки, побывав в каждой клетке ровно один раз, и вернуться в начальную клетку. При этом на доске выделены две соседние клетки: $$$(x_1, y_1)$$$, $$$(x_2, y_2)$$$. В обходе доски королем клетки $$$(x_1, y_1)$$$ и $$$(x_2, y_2)$$$ должны встречаться подряд: оказавшись в одной из них, он должен сразу же перейти в другую.
Найдите подходящий порядок обхода доски или выясните, что его не существует.
Первая строка содержит два числа $$$n$$$ и $$$m$$$ ($$$2 \le n, m \le 1000$$$) — размеры доски.
Вторая строка содержит четыре числа $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$ — координаты двух соседних клеток ($$$1 \le x_1, x_2 \le n$$$; $$$1 \le y_1, y_2 \le m$$$; $$$|x_1-x_2|+|y_1-y_2|=1$$$).
Если такого обхода доски не существует, выведите одно число $$$-1$$$.
Иначе выведите $$$n \times m + 1$$$ пару чисел — координаты клеток в порядке обхода, начальную клетку необходимо вывести дважды, в начале и в конце.
В этой задаче 50 тестов, каждый оценивается независимо в 2 балла.
В этой задаче во время тура вам сообщается результат проверки на каждом тесте.
4 32 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
3 51 2 2 2
-1
На рисунке показан обход доски для первого примера.
