A2. Бинарная таблица (сложная версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Различие между версиями заключается ограничениях на количество операций. Вы можете делать взломы, если обе версии задачи сданы.

Вам дана бинарная таблица размера $$$n \times m$$$. Эта таблица состоит из символов $$$0$$$ и $$$1$$$.

Вы можете делать следующую операцию: выбрать $$$3$$$ различные клетки, которые принадлежат одному квадрату $$$2 \times 2$$$, и изменить символы в этих клетках (поменять $$$0$$$ на $$$1$$$ и $$$1$$$ на $$$0$$$).

Ваша задача сделать все символы таблицы равными $$$0$$$ за не больше чем $$$nm$$$ операций. Вам не нужно минимизировать количество операций.

Можно доказать, что это всегда возможно.

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

В первой строке находится единственное целое число $$$t$$$ ($$$1 \leq t \leq 5000$$$) — количество наборов входных данных. В следующих строках находится описание наборов входных данных.

В первой строке описания каждого набора входных данных находится два целых числа $$$n$$$, $$$m$$$ ($$$2 \leq n, m \leq 100$$$).

Каждая из следующих $$$n$$$ строк содержит бинарную строку длины $$$m$$$, равную очередной строке таблицы.

Гарантируется, что сумма $$$nm$$$ по всем наборам входных данных не превосходит $$$20000$$$.

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

Для каждого набора входных данных выведите целое число $$$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$$$.

Пример
Входные данные
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
Примечание

В первом наборе входных данных можно сделать одну операцию с клетками $$$(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