Problem Description

Little S has a chessboard of size $n \times m$. Initially, each position on the board has a chess piece. Each time, Little S can remove a chess piece if the number of surrounding (four-connected) removed chess pieces does not exceed 1. Determine the maximum number of chess pieces Little S can remove and construct a valid sequence of removals.

Input Format

A single line containing two positive integers $n$ and $m$, representing the size of the chessboard.

Output Format

The first line contains a positive integer, representing the maximum number of chess pieces that can be removed, denoted as $ans$.

The following $n$ lines, each containing $m$ integers between $-1$ and $ans$. Each integer indicates the sequence number of the removal for the chess piece at that position. If the chess piece is not removed, output $-1$.

Sample Input and Output

Sample Input #1

2 2

Sample Output #1

3
1 2
3 -1

Sample Input #2

3 5

Sample Output #2

12
2 3 4 5 6
1 -1 12 -1 7
8 9 -1 11 10

Notes

Sample Explanation

For Sample #1, when removing $(1,1)$, there are 0 removed positions around it. When removing $(1,2)$ and $(2,1)$, there is 1 removed position around each, so the original construction meets the requirements.

It is easy to prove that there is no better solution.

Data Range

This problem uses batched testing.

For 100% of the data: $\bm{1 \leq n \leq 3}$, $1 \leq m \leq 10^5$.

If you correctly answer the first part about the maximum number of removable chess pieces but fail to construct the sequence correctly, you will receive 70% of the score. The score for a subtask is the minimum score of all test cases. Note that you still need to output $n \times m$ numbers indicating the construction sequence; we recommend you output all $-1$.

The checker.cpp is guaranteed to run within 0.5 seconds under the correct output format.

见题面 Input 部分

见题面 Output 部分