Золоте поле

Козак Вус випадково знайшов прямокутне поле розміром $n\times m$ квадратних метрів. Поле має $n$ рядків та $m$ стовпчиків. Рядки нумеруються від $1$ до $n$ зверху вниз. Стовпці нумеруються від $1$ до $m$ зліва направо.

Козак помітив, що у деяких квадратах є золоті монетки, а саме: у квадраті, який знаходиться у $i$-му рядку та $j$-му стовпчику, є рівно $a_{ij}$ золотих монеток.

Просто забрати усі монетки — це занадто легко для Вуса, тому він вирішив, що забере усі монетки з квадратів, у яких кількість монеток парна.

Проте і така задача виявилася занадто легкою для нього, тому Козак Вус вирішив, що буде зсувати монетки: він може взяти усі монетки у якомусь квадраті та перекласти їх у будь-який сусідній квадрат. Квадрати вважаються сусідніми, якщо у них є спільна сторона. Описану операцію зсуву він може виконувати будь-яку кількість разів.

Тепер Козаку цікаво, яку максимальну кількість монет він може забрати. Допоможіть йому знайти цю кількість, а також допоможіть йому зрозуміти, як йому потрібно зсувати монетки, щоб забрати таку кількість.

Зверніть увагу, що Козаку не потрібно мінімізувати кількість операцій зсуву, йому потрібно лише максимізувати кількість монеток, які він забере.

Вхідні дані

Перший рядок містить два цілі числа $t$ та $g$ ($1\le t\le 10$, $0\le g\le 6$) — кількість тестів та номер блока.

Перший рядок кожного тесту містить два цілі числа $n$ та $m$ ($1\le n,m\le 50$) — розміри поля.

Кожен з наступних $n$ рядків містить $m$ цілих чисел $a_{i1},a_{i2},\dots ,a_{im}$ ($0\le a_{ij}\le 100$) — кількості золотих монеток у квадратах.

Не гарантується те, що є принаймні одна монетка на полі.

Вихідні дані

Для кожного тесту виконайте наступне:

У першому рядку виведіть одне ціле число — максимальну кількість монет, яку забере Вус.

У другому рядку виведіть одне ціле число $p$ ($0\le p\le 10000$) — кількість операцій зсуву, які необхідно виконати. Зверніть увагу, що не потрібно мінімізувати значення $p$.

У кожному з наступних $p$ рядків виведіть по чотири цілі числа $x_1$, $y_1$, $x_2$, $y_2$ ($1\le x_1,x_2\le n$, $1\le y_1,y_2\le m$), які означають, що монетки, які знаходяться у квадраті ($x_1$, $y_1$), потрібно зсунути у квадрат ($x_2$, $y_2$).

Якщо існує кілька правильних відповідей, дозволяється вивести будь-яку з них. Гарантується, що існує оптимальна відповідь, де кількість операцій зсуву не перевищує $10000$.

Приклади

Примітка

У першому прикладі Козак може спочатку зсунути усі монетки з квадрата $(1,2)$ у $(2,2)$, після чого поле виглядатиме так:

4 0 1
9 7 0

Після зсуву монеток з $(2,2)$ у $(2,1)$ поле виглядатиме так:

4  0 1
16 0 0

Тому відповідь $4+16=20$.

У другому прикладі Козак може спочатку зсунути усі монетки з квадрата $(1,1)$ у $(1,2)$, після чого поле виглядатиме так:

0 5 5  4

Після зсуву монеток з $(1,2)$ у $(1,3)$ поле виглядатиме так:

0 0 10 4

Тому відповідь $10+4=14$.

Оцінювання

1. ($14$ балів) $n=1$, усі $a_{ij}$ парні;

2. ($16$ балів) $n=1$, усі $a_{ij}$ непарні;

3. ($19$ балів) $n=1$;

4. ($14$ балів) $n,m>1$, усі $a_{ij}$ парні;

5. ($17$ балів) $n,m>1$, усі $a_{ij}$ непарні;

6. ($20$ балів) $n,m>1$.