Signals

Task

The International Computer College of Bucharest has a network of $N$ computers linked in a circle. Computer $i$ (for $1 \leq i < 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.

Constraints

• $1 \leq T \leq 100 \ 000$
• $2 \leq N$
• $2 \leq N \cdot K \leq 5 \ 000 \ 000$
• $0 \leq W_i \leq K$
• It is guaranteed that the sum of $N \cdot K$ 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 of the subtask.
• Let $W_{max}$ be the maximum value among all $W_i$'s.

Example

stdin

3
5 3
2 1 3 0 2
10 6
3 2 1 4 3 2 1 3 2 1
2 3
2 1

stdout

YES
000
110
010
101
101
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. There- fore, NO is printed.