题目描述

Once, s1mple approached Kostya, a well-known problem solver, and said:

$\textit{If you want to become better, you need constant practice. Here is a problem for training:}$

Given a matrix $a$ of size $n \times m$ ($n$ --- number of rows; $m$ --- number of columns), where each element is either $0$ or $1$. It is known that each column contains exactly $c_i$ ones. The elements within each column can be arranged freely. The goal is to maximize the number of rows with an odd number of ones and to find such a matrix.

Kostya silently nodded, sat down at the table, and began to work, knowing that every practice brings him closer to mastery.

Kostya couldn't solve the problem and is asking you to help him solve it.

$\textbf{You can earn partial points if you only find the number, not the matrix. More details below.}$

输入格式

The first line contains two integers $n$ and $m$ $(1 \le n \cdot m \le 10^6)$ --- the dimensions of the matrix.

The second line contains $m$ integers $c_1, c_2, \dots, c_m$ $(0 \le c_i \le n)$ --- the number of ones in each column.

输出格式

In the first line, output a single integer $t$ ($0 \leq t \leq n$) --- the number of rows in the matrix with an odd sum.

In each of the next $n$ lines, output $m$ integers $a_{ij}$ ($0 \leq a_{ij} \leq 1$) --- the numbers of the matrix.

8 4
6 1 6 1

6
1 1 1 0 
1 0 1 1 
1 0 1 0 
1 0 1 0 
1 0 0 0 
1 0 0 0 
0 0 1 0 
0 0 1 0 

4 4
3 0 3 0

2
1 0 1 0 
1 0 1 0 
1 0 0 0 
0 0 1 0 

7 3
4 3 2

7
1 1 1 
1 0 0 
1 0 0 
1 0 0 
0 1 0 
0 1 0 
0 0 1 

提示

In the first example, the first and third columns intersect in at least $4$ positions, meaning that if there were only these two columns, we would have $4$ even rows, but since there are also two columns with $1$ one, we can convert two of them to odd, so the optimal answer will be $6$ odd rows.

In the second example, we can ignore the second and fourth columns because they have no ones, meaning they will not change the parity of any row, and the first and third intersect in at least $2$ rows, meaning at least two rows will be even, so the answer is $2$.

In the third example, the answer is $7$, because there exists a matrix that has $7$ odd rows and satisfies the condition, and there is no matrix that has more than $7$.

Scoring

• ($10$ points): $n, m \le 5$;
• ($8$ points): the number of ones in the matrix does not exceed $n$;
• ($20$ points): the number of ones in each column does not exceed $n/2$;
• ($14$ points): $n, m \le 50$;
• ($14$ points): $n \le 3\,000$;
• ($14$ points): $n \cdot m \le 3\cdot10^5$;
• ($20$ points): no additional restrictions.

You can earn half the points for each block if you output the correct $t$ for each test in the block.

Note that to earn partial points, you need to output the correct $t$ and

• either output nothing more; that is, output only $t$, but not the matrix;
• or output the complete matrix consisting of $0$s and $1$s, which does not have to be correct. For example, one that consists entirely of zeros.

If you output, for example, only a few rows, or too many rows, numbers other than $0$ and $1$, etc., you will receive $0$ points.