Signals — RMI contest
Task type: batch | Time limit: 1.2 s | Memory limit: 512 MB | Difficulty: 21
Algorithms: linear algebra, combinatorics, constructive, binary matrix

# Problem: Signals

Romanian Master of Informatics, Day 2
Bucharest, Romania
Friday 29th November, 2024

**Input file:** `stdin`  
**Output file:** `stdout`

The International Computer College of Bucharest has a network of $N$ computers linked in a circle. Computer $i$ (for $1 \le i \le N$) is connected with computer $i + 1$ through link $i$. Computers $N$ and $1$ are also connected through link $N$.

Each computer has a security key comprising $K$ bits of information, represented as a binary string of length $K$. Each link $i$ also has a security threshold $W_i$. The two computers connected through this link can only communicate if their security keys differ in *exactly* $W_i$ positions.

The system administrator has lost the security keys and needs your help to generate new ones in such a way that communication can take place through every link.

## Input Data

The first line of the input contains $T$ — the number of testcases to solve. The description of $T$ testcases follows.

The first line of a testcase contains two space-separated integers $N$, $K$. The second line of a testcase contains $N$ space-separated integers $W_1, W_2, \dots, W_N$.

## Output Data

Output the answers for the $T$ testcases. The description of an answer for a testcase follows.

If there is no solution for a testcase, the first and only line of the output must contain the string `NO`. Otherwise, the first line of the output must contain the string `YES`, and lines 2 to $N + 1$ must contain a valid list of security keys. The security key for each computer $i$ must be printed as a binary string without any spaces on the $(i + 1)$th line.

## Restrictions

*   $1 \le T \le 100\,000$
*   $2 \le N$
*   $2 \le NK \le 5\,000\,000$
*   $0 \le W_i \le K$
*   It is guaranteed that the sum of $NK$ among all testcases doesn't exceed $5\,000\,000$.
*   If you correctly determine whether or not a solution exists, yet you output incorrect security keys (but which are correctly formatted), then you will be awarded 50% of the points for the subtask.
*   Let $W_{max}$ be the maximum value among all $W_i$'s.

## Subtasks

| # | Points | Restrictions                     |
|---|--------|----------------------------------|
| 1 | 5      | $T, N, K \le 5$  |
| 2 | 2      | $K = 1$                          |
| 3 | 8      | $K = 2$                          |
| 4 | 32     | $2W_{max} \le K$                 |
| 5 | 24     | $N \le 50\,000$, $K \le 20$ |
| 6 | 29     | No further restrictions.         |

## Examples

| Input file          | Output file |
|---------------------|-------------|
| `3`                   | `YES`         |
| `5 3`                 | `000`         |
| `2 1 3 0 2`           | `110`         |
| `10 6`                | `010`         |
| `3 2 1 4 3 2 1 3 2 1` | `101`         |
| `2 3`                 | `101`         |
| `2 1`                 | `YES`         |
|                     | `000000`      |
|                     | `111000`      |
|                     | `111110`      |
|                     | `111111`      |
|                     | `000011`      |
|                     | `111011`      |
|                     | `011111`      |
|                     | `111111`      |
|                     | `000111`      |
|                     | `000001`      |
|                     | `NO`          |

## Explanation

For the first testcase, the security key `000` differs in 2 bits/positions from `110`, `110` differs in 1 bit from `010`, `010` differs in 3 bits from `101`, `101` differs in 0 bits from `101`, and `101` differs in 2 bits from `000`, satisfying all five security thresholds.

For the last testcase, there isn't a way to choose security keys such that all conditions are met. Therefore, `NO` is printed.

Starter code: