题目描述

题目译自 Ukrainian Olympiads in Informatics 2020 Stage 4 Day2 T1. Золоте поле

科扎克·武斯偶然发现了一块 $n \times m$ 平方米的矩形田地。田地有 $n$ 行和 $m$ 列。行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $m$。

科扎克注意到，有些方格中藏有金币，具体来说，位于第 $i$ 行第 $j$ 列的方格中有 $a_{ij}$ 枚金币。

直接拿走所有金币对武斯来说太简单了，因此他决定只拿走金币数量为偶数的方格中的金币。

然而，这个任务对他来说仍然太简单，于是科扎克·武斯决定移动金币：他可以选择一个方格中的所有金币，并将其移动到任意一个相邻的方格。相邻方格是指有公共边的方格。他可以任意多次执行这种移动操作。

现在，科扎克想知道他能拿走的最大金币数量。请帮助他计算这个数量，并帮助他弄清楚如何移动金币以达到这个数量。

请注意，科扎克不需要最小化移动操作的次数，他只需要最大化他能拿走的金币数量。

输入格式

第一行包含两个整数 $t$ 和 $g$ $(1 \leq t \leq 10, 0 \leq g \leq 6)$，分别表示输入数据组数和子任务编号。

每组输入数据的第一行包含两个整数 $n$ 和 $m$ $(1 \leq n, m \leq 50)$，表示田地的尺寸。

接下来的 $n$ 行，每行包含 $m$ 个整数 $a_{i1}, a_{i2}, \dots, a_{im}$ $(0 \leq a_{ij} \leq 100)$，表示每个方格中的金币数量。

不保证田地上至少有一个金币。

输出格式

对于每组输入数据，按以下格式输出：

第一行输出一个整数，表示武斯能拿走的最大金币数量。

第二行输出一个整数 $p$ $(0 \leq p \leq 10000)$，表示需要执行的移动操作次数。请注意，不需要最小化 $p$ 的值。

接下来的 $p$ 行，每行包含四个整数 $x_1, y_1, x_2, y_2$ $(1 \leq x_1, x_2 \leq n, 1 \leq y_1, y_2 \leq m)$，表示将位于方格 $(x_1, y_1)$ 的金币移动到方格 $(x_2, y_2)$。

如果存在多种正确答案，可以输出任意一种。保证存在一种最优答案，其中移动操作次数不超过 $10000$。

2 0
2 3
4 5 1
9 2 0
1 4
1 4 5 4

20
4
1 1 2 1
1 2 2 2
2 1 2 2
2 2 2 3
14
3
1 1 1 2
1 2 1 3
1 3 1 4

在第一个样例中，科扎克可以先将方格 $(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$。

数据范围与提示

详细子任务附加限制及分值如下表所示：