Это сложная версия задачи. Различие между версиями заключается ограничениях на количество операций. Вы можете делать взломы, если обе версии задачи сданы.
Вам дана бинарная таблица размера \(n \times m\). Эта таблица состоит из символов \(0\) и \(1\).
Вы можете делать следующую операцию: выбрать \(3\) различные клетки, которые принадлежат одному квадрату \(2 \times 2\), и изменить символы в этих клетках (поменять \(0\) на \(1\) и \(1\) на \(0\)).
Ваша задача сделать все символы таблицы равными \(0\) за не больше чем \(nm\) операций. Вам не нужно минимизировать количество операций.
Можно доказать, что это всегда возможно.
Выходные данные
Для каждого набора входных данных выведите целое число \(k\) (\(0 \leq k \leq nm\)) — количество операций.
В каждой из следующих \(k\) строк выведите \(6\) целых чисел \(x_1, y_1, x_2, y_2, x_3, y_3\) (\(1 \leq x_1, x_2, x_3 \leq n, 1 \leq y_1, y_2, y_3 \leq m\)), описывающих следующую операцию. Эта операция будет сделана с тремя клетками \((x_1, y_1)\), \((x_2, y_2)\), \((x_3, y_3)\). Все три клетки должны быть различны. Эти три клетки должны лежать в каком-то квадрате \(2 \times 2\).
Примечание
В первом наборе входных данных можно сделать одну операцию с клетками \((1, 1)\), \((2, 1)\), \((2, 2)\). После этого, все символы будут равны \(0\).
Во втором наборе входных данных:
- операция с клетками \((2, 1)\), \((3, 1)\), \((3, 2)\). После этой операции таблица будет:
011
001
000
- операция с клетками \((1, 2)\), \((1, 3)\), \((2, 3)\). После этой операции таблица будет:
000
000
000
В пятом наборе входных данных:
- операция с клетками \((1, 3)\), \((2, 2)\), \((2, 3)\). После этой операции таблица будет:
010
110
- операция с клетками \((1, 2)\), \((2, 1)\), \((2, 2)\). После этой операции таблица будет:
000
000
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 2
10
11
3 3
011
101
110
4 4
1111
0110
0110
1111
5 5
01011
11001
00010
11011
10000
2 3
011
101
|
1
1 1 2 1 2 2
2
2 1 3 1 3 2
1 2 1 3 2 3
4
1 1 1 2 2 2
1 3 1 4 2 3
3 2 4 1 4 2
3 3 4 3 4 4
4
1 2 2 1 2 2
1 4 1 5 2 5
4 1 4 2 5 1
4 4 4 5 3 4
2
1 3 2 2 2 3
1 2 2 1 2 2
|