Description

There is a chessboard with $n$ rows and $m$ columns, with a total of $n m$ cells. Please place pieces in the cells (each cell can contain at most one piece) such that for all $1 \le i \le m$, the $i$-th column contains exactly $a_i$ pieces. In addition, any two pieces on the chessboard must not be edge-adjacent.

Determine whether a valid arrangement exists. If it exists, output any valid arrangement.

Input Format

The first line contains two positive integers $n, m$, and it is guaranteed that $n \le 300, m \le 300$.
The second line contains $m$ non-negative integers $a_1, a_2, \ldots , a_m$, and it is guaranteed that $0 \le a_i \le n$.

Output Format

If there is no solution, output a string No.
If there is a solution, output a string Yes on the first line, then output $n$ lines, each containing a string of length $m$ representing the chessboard arrangement you construct. Here, 0 means an empty cell, and 1 means a cell with a piece.

3 4
2 1 2 1

Yes
1010
0101
1010

3 4
2 3 3 3

No

Hint

[Source]

From the preliminary round of the 2021 Tsinghua University Student Algorithm Competition and Collegiate Invitational Contest (THUPC2021).

Resources such as solutions can be found at https://github.com/THUSAAC/THUPC2021-pre.

Translated by ChatGPT 5