Сізде нөлдер мен бірліктерден тұратын кесте бар. Кестені тазарту үшін барлық бірліктерді нөлдерге айналдыруды қалайсыз.

Бірақ бір ереже бар: бір қадамда сіз бір қатарда немесе бір бағанда орналасқан екі әртүрлі ұяшықты таңдай аласыз және олардың мәндерін қарама-қарсы етіп ауыстырасыз:

• егер ұяшықта \(0\) болса, ол \(1\) болады;

• егер \(1\) болса, ол \(0\) болады.

Сіздің міндетіңіз — мүмкіндігінше аз қадамдармен кестені тазарту. Кейде тазарту мүмкін болмайды.

Әр тестте \(T\) параметрі көрсетіледі:

• егер \(T = 0\), тек минималды қадамдар санын шығару керек;

• егер \(T = 1\), операциялардың тізімін де шығару керек.

Операция екі ұяшықты таңдап, олардың мәндерін бір уақытта инверсиялауды білдіреді.

Енгізу

Бірінші жолда бір бүтін сан \(t\) \((1 \le t \le 100)\) — тестілер саны.

Келесі жолдарда тестілердің сипаттамалары беріледі.

Әр тест мыналардан тұрады:

• үш бүтін саннан тұратын бір жол \(n\), \(m\), \(T\) \((1 \le n \cdot m \le 3 \cdot 10^5,\ T \in \{0, 1\})\) — кестенің өлшемдері және шығару түрі;

• \(n\) жол, әрқайсысында \(m\) символ \(0\) немесе \(1\) — кестенің сипаттамасы.

Барлық тестілер бойынша ұяшықтардың жалпы саны \(3 \cdot 10^5\)-тен аспайтынына кепілдік беріледі.

Шығару

Әр тест үшін:

• Егер кестені тазарту мүмкін болмаса, -1 шығарыңыз.

• Әйтпесе, егер \(T = 0\), бір бүтін сан \(k\) — минималды қадамдар санын шығарыңыз.

• Әйтпесе, егер \(T = 1\), бірінші жолда \(k\) шығарыңыз, содан кейін \(k\) жолда \(4\) бүтін сан \(r_1\ c_1\ r_2\ c_2\) — осы қадамда инверсияланған ұяшықтардың координаттары \((1 \le r_1, r_2 \le n;\ 1 \le c_1, c_2 \le m)\).

Бірнеше дұрыс жауап болса, кез-келгенін шығаруға болады.

Бағалау жүйесі

Мысалдар

Енгізу 1

3
2 3 0
101
110
1 4 1
0010
2 2 1
10
01

Жауап 1

2
-1
2
1 1 2 1
2 1 2 2

Ескертпелер

Бірінші тест:

Екі қадам жасауға болады:

• \((1,1)\) және \((1,3)\) ұяшықтарын инверсиялау — \(1\)-ші қатар \([0\ 0\ 0]\) болады.

• \((2,1)\) және \((2,2)\) ұяшықтарын инверсиялау — \(2\)-ші қатар \([0\ 0\ 0]\) болады.

Жауап: 2

Үшінші тест:

Матрицаны екі қадамда нөлге айналдыруға болады:

• \((1,1)\) және \((2,1)\) ұяшықтарын инверсиялау — \(1\)-ші баған \([0\ 1]\) болады.

• \((2,1)\) және \((2,2)\) ұяшықтарын инверсиялау — \(2\)-ші қатар \([0\ 0]\) болады.

Жауап: 2