Немного отвлечемся от второй части истории и вспомним первую. Человек-паук Нуар оказался очень заинтересован кубиком Рубика, и решил во что бы то ни стало разгадать все тайны этого загадочного предмета. Но вот незадача — до сих пор он так и не смог выяснить, что это за странное устройство, и в чем его предназначение.
Поэтому он решил потренироваться на черно-белой версии кубика Рубика, при чем еще и двумерной, а не трехмерной. Для этого он взял клетчатую табличку размера $$$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