Человек-паук Нуар и кубик Рубика
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Немного отвлечемся от второй части истории и вспомним первую. Человек-паук Нуар оказался очень заинтересован кубиком Рубика, и решил во что бы то ни стало разгадать все тайны этого загадочного предмета. Но вот незадача — до сих пор он так и не смог выяснить, что это за странное устройство, и в чем его предназначение.

Поэтому он решил потренироваться на черно-белой версии кубика Рубика, при чем еще и двумерной, а не трехмерной. Для этого он взял клетчатую табличку размера $$$n \times m$$$, каждая клетка которого закрашена либо в черный, либо в белый цвет. Как и в кубике Рубика, цвета элементов можно менять, но вместо вращения с этой таблицей можно делать одну из двух операций:

Конечная цель — добиться того, чтобы существовал «путь» по черным клеткам из левого верхнего угла таблицы в правый нижний с шагами на один вправо и шагами на один вниз. Иными словами, должна существовать такая последовательность черных клеток $$$(r_1, c_1), (r_2, c_2), \ldots, (r_{n+m-1}, c_{n+m-1})$$$, что

Определите минимальное число действий, необходимое для получения такого пути, или скажите, что получить такой путь из черных клеток невозможно. Человек-паук Нуар очень расчитывает на вашу помощь.

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

В первой строке ввода через пробел даны два целых числа $$$n$$$ и $$$m$$$ — высота и ширина таблицы ($$$1 \le n, m \le 2000$$$).

В $$$i$$$-й из следущих $$$n$$$ строк записаны $$$m$$$ символов, каждый из которых равен '0' или '1' — обозначения цветов клеток в $$$i$$$-й строке таблицы. Символ '0' означает белый цвет, а '1' — черный.

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

Если невозможно, инвертируя строки и столбцы, получить черный путь из левой верхней клетки таблицы до правой нижней, выведите единственное число -1.

Иначе, в первой строке выведите через пробел два целых числа $$$r$$$ и $$$c$$$ — количество инвертируемых строк и столбцов, соответственно. После чего во второй строке выведите через пробел $$$r$$$ номеров инвертируемых строк, а в третьей строке — $$$c$$$ номеров инвертируемых столбцов.

Строки и столбцы нумеруются с $$$1$$$ (строки — сверху вниз, столбцы — слева направо). Выводить номера строк и столбцов можно в любом порядке. Среди всех ответов, минимизирующих $$$r + c$$$, можно выбрать любой.

Примеры

Входные данные
2 2
10
01
Выходные данные
1 1
1 
1 
Входные данные
4 4
1111
0001
0001
0000
Выходные данные
1 0
4 

Входные данные
3 5
10000
01010
00001
Выходные данные
2 1
2 1 
1