Maximize Connected Ones in Matrix

Given two positive integers n and m, consider an n × m matrix. You need to fill the matrix with 0s and 1s subject to the following constraints:

• No four consecutive cells in any row or column may contain the same number. In other words, in every row and every column, any contiguous block of identical numbers must have a length of at most 3. Formally, for any row i and any consecutive indices j, j+1, j+2, j+3, it is not allowed that \[ a_{i,j} = a_{i,j+1} = a_{i,j+2} = a_{i,j+3}. \]
• The cells containing 1 must form a connected region. Two cells are considered adjacent if they share an edge. That is, for any two cells containing 1, there should exist a path moving only up, down, left, or right that connects them while staying within cells containing 1.

Your task is to construct a matrix satisfying these conditions that has as many 1s as possible. Then, output the maximum number of 1s in the matrix, followed by the matrix itself.

inputFormat

The input consists of a single line with two space-separated integers n and m (1 ≤ n, m ≤ 300), representing the number of rows and columns of the matrix.

outputFormat

Output the maximum number of 1s on the first line. Then, print n lines with m integers each (either 0 or 1), representing the matrix. The numbers in each row should be separated by a space.

sample

1 1

1
1