406353: GYM102386 J Катамари

J. Катамариограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

«Катамари» — это магический шар, к которому прилипает всё, что его касается. Он катится по Земле, собирая всё большие и большие объекты, пока не вырастет достаточно громадным, чтобы стать новым небесным телом.

В этот раз катамари занесло на прямоугольное клетчатое поле размера $$$n$$$ строк на $$$m$$$ столбцов. Будем говорить, что клетка, находящаяся в строке $$$i$$$ в столбце $$$j$$$, имеет координаты $$$(i, j)$$$ ($$$1 \le i \le n$$$, $$$1 \le j \le m$$$). В каждой клетке расположен какой-нибудь объект. Размер объекта, находящегося в клетке с координатами $$$(i, j)$$$, равен $$$a_{ij}$$$. При этом мир настолько разнообразен, что для любого числа существует не более трёх объектов такого размера.

Ваша задача — прицепить все объекты, перекатывая катамари по полю. Начать можно в любой клетке. Две клетки называются соседними, если номера их столбцов совпадают, а номера строк отличаются на единицу, либо если номера их строк совпадают, а номера столбцов отличаются на единицу. Перемещаться из клетки можно только в соседнюю клетку, выходить за пределы поля нельзя. При этом одну клетку нельзя посещать дважды.

Необходимо также выполнить следующее ограничение: размеры объектов, прицепленные к катамари, должны нестрого возрастать. Иными словами, для любых двух объектов разного веса, меньший из них должен быть приклеен раньше, чем больший.

Составьте такой маршрут для катамари, чтобы каждый объект был собран, и все ограничения были выполнены.

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

В первой строке через пробел вводятся два целых числа $$$n$$$ и $$$m$$$  — размеры поля ($$$1 \leq n, m \leq 100$$$).

Следующие $$$n$$$ строк описывают поле. В каждой из них содержится $$$m$$$ целых чисел $$$a_{ij}$$$, разделённых пробелом ($$$1 \leq a_{ij} \leq 10^4$$$) — размеры объектов в соответствующих клетках.

Гарантируется, что для любого числа существует не более трёх объектов такого размера.

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

Если составить требуемый маршрут невозможно, в единственной строке выведите $$$-1$$$.

Иначе, выведите $$$n \cdot m$$$ строк. В $$$k$$$-й строке через пробел выведите два числа $$$i_k$$$ и $$$j_k$$$  — координаты $$$k$$$-й клетки маршрута. Маршрут должен обходить всё поле, не посещая одну клетку дважды, а размеры объектов в порядке обхода должны составлять неубывающую последовательность. Если возможных ответов несколько, выведите любой из них.

ПримерыВходные данные

2 4
1 4 8 16
2 4 16 16

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

1 1
2 1
2 2
1 2
1 3
1 4
2 4
2 3

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

3 3
1 2 2
1 2 3
1 3 3

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

-1