There is a grid with $n$ columns and $m$ rows, with the top-left corner at $(0, 0)$ and the bottom-right corner at $(n, m)$. You are to cover all edges using two types of L-shaped tiles. Each edge must be covered exactly once by one L-shaped tile. You must output a valid covering scheme and use the minimum possible number of L-shaped tiles. The two types of L-shaped tiles consist of two segments of length $1+1$ and two segments of length $1+2$ (see Figure 1 for detailed shapes).
Input
The input is read from the file cover.in.
The first line contains an integer $T$, representing the number of test cases.
The next $T$ lines each contain two integers $n, m$, representing the grid size.
Output
The output is written to the file cover.out.
For each test case, the first line should output the number of L-shaped tiles used, $k$.
The next $k$ lines each output one L-shaped tile. An L-shaped tile is represented by three integers $x, y, t$, where $x, y$ represent the intersection point of the two segments of the L-shaped tile, and $t$ represents the ID of the L-shaped tile. See Figure 1 for details. The blue numbers indicate the ID of the L-shaped tile above the number.
Figure 1: Each type of L-shaped tile and its ID
Examples
Input 1
2 2 2 2 3
Output 1
4 2 2 8 1 2 8 0 1 1 0 0 1 6 1 3 6 0 2 1 2 3 8 2 1 7 1 0 2 0 0 2
Note
The covering scheme for the first test case in the example is shown in Figure 2. It uses 4 L-shaped tiles.
Figure 2: Covering scheme for the first test case
The covering scheme for the second test case in the example is shown in Figure 3. It uses 6 L-shaped tiles.
Figure 3: Covering scheme for the second test case
Constraints
For all test data, it is guaranteed that $1 \le n \times m \le 10^5$ and $\sum n \times m \le 5 \times 10^5$.
| Test Case ID | $\min(n, m)$ | $\max(n, m)$ |
|---|---|---|
| 1 | $= 1$ | $\le 500$ |
| 2 | $\le 10^5$ | |
| 3 | $= 2$ | $\le 500$ |
| 4 ~ 5 | $\le 10^5$ | |
| 6 | $= 3$ | $\le 500$ |
| 7 ~ 8 | $\le 10^5$ | |
| 9 ~ 10 | $\le 10^5$ | $\le 9$ |
| 11 ~ 12 | $\le 16$ | |
| 13 ~ 16 | $\ge 4$ | $\le 10^5$ |
| 17 ~ 20 | $\le 10^5$ | $\le 10^5$ |
Subtasks
This problem has partial scoring. For all data in a test case, if the output scheme is valid and uses the minimum number of L-shaped tiles, you will receive 100% of the points for that test case. If the output scheme is valid but some data does not use the minimum number of L-shaped tiles, you will receive 20% of the points for that test case. If the output scheme is invalid, you will receive 0 points for that test case.
Implementation Details
In the contestant's directory, cover/check.cpp can be used to check if your output is correct and to output the number of L-shaped tiles used. You can use the following command to compile the checker:
g++ -std=c++14 -O2 -o check check.cpp
Use the following command in Linux to check your output:
./check <input-file> <output-file>
Or use the following command in Windows to check your output:
check.exe <input-file> <output-file>
Where <output-file> is your output and <input-file> is the input corresponding to your output.
The program will output a check log to standard output, with one line of log for each test case in the input. The logs have three levels:
- CRITICAL: Indicates that the checker encountered an unrecoverable error, such as incorrect runtime arguments or failure to open input/output files. After outputting this type of log, the checker will stop immediately.
- ERROR: Indicates that the output covering scheme is invalid. The checker will output the reason for the error, but this will not terminate the checker.
- INFO: Indicates that the output covering scheme is valid. The checker will also output the number of L-shaped tiles used.