Chessboard Inversion

Little Dima gave his little brother Petya an interactive chessboard of size \(n \times m\) as a present. The board is initially colored in chess style; that is, every cell is either black or white and every two cells sharing a side have different colors. Petya can choose any rectangular sub-board and perform an inversion on it: every white cell in the chosen rectangle becomes black and every black cell becomes white.

Petya’s goal is to make all the cells of the board have the same color using as few inversion operations as possible. Help him obtain a sequence of inversions with a minimal number of moves.

Note: The operation is specified by four integers \(r_1, c_1, r_2, c_2\) which denote the top‐left and bottom‐right corners (using 1-indexing) of the rectangle to invert. You may assume the initial board is colored in a standard chessboard pattern where the cell at (1,1) is white.

Hint:

• If \(n = 1\) or \(m = 1\) (a one‐dimensional board with at least 2 cells) the answer is equivalent to solving the following 1D problem on an alternating binary sequence. In such a sequence the minimal number of contiguous inversion operations needed is \(\left\lceil\frac{L-1}{2}\right\rceil\) for a sequence of length \(L\) if you choose the optimal target color.
• If \(n \ge 2\) and \(m \ge 2\) a solution with 2 inversions always exists. For example, one may invert the entire second column and then the entire second row to make all cells white.

The answer should output the minimal number of inversions \(k\) in the first line, followed by \(k\) lines each containing four integers \(r_1\, c_1\, r_2\, c_2\) representing an inversion operation.

All formulas are given in \(\LaTeX\) format.

inputFormat

The input consists of one line containing two integers \(n\) and \(m\) \((1 \le n, m \le 1000)\) -- the number of rows and columns of the chessboard.

For example:

2 3

outputFormat

Output the minimal number of inversion operations \(k\) needed to make the board uniform, on the first line. Then output \(k\) lines, each containing four space‐separated integers \(r_1\, c_1\, r_2\, c_2\) which specify the operation to invert the rectangle with top–left cell \((r_1, c_1)\) and bottom–right cell \((r_2, c_2)\). Use 1-indexing.

sample

1 1

0