题目描述

暴暴龙国的交通网络大小可以用两个正整数 $n,m$ 表示。有 $(n+1)\times(m+1)$ 个路口：对于任意 $0\le i\le n$，$0\le j\le m$，都有一个十字路口 $(i,j)$。地图上，$i$ 越大，路口的位置越靠右；$j$ 越大，路口的位置越靠下。路口之间形成网格状的道路，即两个 $i$ 相同且 $j$ 相邻的路口之间有一条道路，两个 $i$ 相邻且 $j$ 相同的路口之间有一条道路。

暴暴龙国的每个士兵可以选择两个相邻的方向，并监管每个方向正整数单位长度的道路，但是两个方向的长度总和不超过 $3$。即每个士兵都有 $12$ 种监管方案，我们将这些方案编号为 $0\sim11$，如下图所示。图中每个直角顶点位置即为士兵的位置。

如果同一个路段同时被两个士兵监管，那么可能会产生冲突。所以暴暴龙神希望任意一个路段都恰好被一个士兵监管。除此之外，暴暴龙神还希望最小化部署的士兵的数量。

你的任务是帮暴暴龙神确定一种部署士兵的方案。

注意：没有最小化士兵的数量也可能获得部分分数。具体请看“评分方式”部分。

本题所有测试点的输入文件可以在下发文件中获取。

简要题意：在给定的 $n\times m$ 网格中，用这 $12$ 种图形不重不漏地覆盖网格的边，最小化使用的图形数量。

输入格式

本题包含多组数据。 输入文件的第一行包含一个正整数 $T$ 表示数据组数。接下来对于每组数据：共一行，包含两个整数 $n,m$。

输出格式

对于每组数据：第一行先输出总士兵数量 $w$。

接下来 $w$ 行，每行包含三个整数 $x,y,t$，表示一个位于 $(x,y)$ 的士兵，监管方案为 $t$。你需要保证 $0\le x\le n$，$0\le y\le m$，$0\le t\le11$，并且部署方案符合题目的要求。

样例 1 输入

1
2 3

样例 1 输出

6
1 3 8
2 3 8
0 2 1
2 1 7
0 0 2
1 0 0

样例 1 解释

样例输出的构造如图所示，其中同一种颜色的道路由同一个士兵监管：

容易证明，不存在比 $6$ 个士兵更少的部署方案。

数据范围

对于所有测试数据保证：

• $1\le T\le10^4$；
• $1\le n,m\le10^5$；
• $\sum n\times m\le10^6$。

本题共包含 $30$ 个测试点。所有测试点的输入文件可以在下发文件中获取。

评分方式

对于每个测试点单独评分，选手在本题获得的总得分为每个测试点分数的加和。

若一个测试点中，存在一组数据选手给出的构造不合法，那么该测试点得 $0$ 分。若一个测试点中，对于每一组数据选手给出的构造方案使用的 $w$ 都是最优的，那么该测试点得满分。否则，选手在每一组数据的得分按照对应的评分方式计算（每个测试点使用的评分方式见“数据范围”部分），测试点的最终得分为每组数据的得分最小值。

设最优解使用的 $w$ 比选手使用的 $w'$ 少 $d=w'-w$。

评分方式 A：除了上述两种默认情形之外，选手在该测试点都得 $0$ 分。

评分方式 B：设测试点满分为 $s$。

• 若 $d\le5$，得 $\frac12(s+1)$ 分；
• 否则，得 $1$ 分。

评分方式 C：

• 若 $d\le5$，得 $3$ 分；
• 若 $d\le220$，得 $2$ 分；
• 否则，得 $1$ 分。

评分方式 D：

• 若 $d\le5$，得 $8$ 分；
• 若 $d\le\max(n,m)+5$，得 $6$ 分；
• 否则，得 $3$ 分。

提示

下发文件中的 checker.cpp 提供了一份示例校验程序。它可以检查你的输出是否正确，并同时输出使用了多少士兵。你可以使用如下命令编译校验程序。

g++ -std=c++14 -O2 -o checker checker.cpp

并使用如下命令检查你的输出。

./checker <input-file> <output-file>

其中 <output-file> 是你的输出，<input-file> 是你的输出对应的输入。

程序会将检查日志输出到标准输出，对于输入的每组测试点输出一行日志。日志有如下三个等级：

• CRITICAL：表示检查程序遇到了无法恢复的错误，如运行参数错误，无法打开输入输出文件等。输出这类日志后，检查程序将立刻停止运行。
• ERROR：表示输出的覆盖方案不合法，检查程序会同时输出错误原因，但这不会结束检查程序。
• INFO：表示输出的覆盖方案合法，检查程序会同时输出使用的士兵数量。

@下发文件