题目描述

哥萨克人 Vus 偶然发现了一块 $n \times m$ 平方米的矩形田地。这块田地有 $n$ 行 $m$ 列，行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $m$。

Vus 注意到某些方格中有金币：位于第 $i$ 行第 $j$ 列的方格中恰好有 $a_{ij}$ 枚金币。

如果只是简单地捡起所有金币，对 Vus 来说太容易了，因此他决定只从金币数量为偶数的方格中收取金币。

然而这个任务对他来说还是太简单，于是 Vus 决定通过以下方式移动金币：他可以将某个方格中的全部金币转移到任意相邻的方格中。两个方格相邻当且仅当它们共享一条边。他可以执行任意次数的这种转移操作。

现在 Vus 想知道他最多能收取多少金币。请你帮他计算这个最大值，并告诉他应该如何移动金币才能达到这个目标。

注意 Vus 不需要最小化转移操作的次数，他只需要最大化最终收取的金币数量。

输入格式

第一行包含两个整数 $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$）——每个方格中的金币数量。

不保证田地中至少有一枚金币。

输出格式

对于每个测试用例，按以下格式输出：

第一行输出一个整数——Vus 能收取的最大金币数量。

第二行输出一个整数 $p$（$0 \leq p \leq 10\,000$）——需要执行的转移操作次数。注意不需要最小化 $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)$ 的方格中。

如果有多个正确答案，输出任意一个即可。题目保证存在最优解，且转移操作次数不超过 $10\,000$。

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

提示

在第一个样例中，Vus 可以先将 $(1, 2)$ 方格中的所有金币转移到 $(2, 2)$，此时田地状态为：

$$\begin{array}{cc} 4 & 0 & 1\\ 9 & 7 & 0\\ \end{array}$$

然后将 $(2, 2)$ 方格中的金币转移到 $(2, 1)$，田地状态变为：

$$\begin{array}{cc} 4 & 0 & 1\\ 16 & 0 & 0\\ \end{array}$$

因此最终收取的金币数量为 $4+16=20$。

在第二个样例中，Vus 可以先将 $(1, 1)$ 方格中的金币转移到 $(1, 2)$，此时田地状态为：

$$\begin{array}{c} 0 & 5 & 5 & 4 \end{array}$$

然后将 $(1, 2)$ 方格中的金币转移到 $(1, 3)$，田地状态变为：

$$\begin{array}{c} 0 & 0 & 10 & 4 \end{array}$$

因此最终收取的金币数量为 $10+4=14$。

评分标准

• （$14$ 分）$n=1$，所有 $a_{ij}$ 为偶数；
• （$16$ 分）$n=1$，所有 $a_{ij}$ 为奇数；
• （$19$ 分）$n=1$；
• （$14$ 分）$n,m>1$，所有 $a_{ij}$ 为偶数；
• （$17$ 分）$n,m>1$，所有 $a_{ij}$ 为奇数；
• （$20$ 分）$n,m>1$。

翻译由 DeepSeek V3 完成