背景

2025/04/16：加入一份 hack 数据（#34）（source）。

题目描述

给定长度为 $n$ 的非负整数序列 $a_1,a_2,\ldots,a_n$ 和正整数 $k$。

你需要构造一个长度为 $n$ 的非负整数序列 $b_1,b_2,\ldots,b_n$，满足：

• $\forall 1\le i\le n$，$b_i\in [0, 2^k)$；
• $\forall 1\le i\le n$，$\operatorname{popcount}(b_i \oplus b_{i\bmod n+1})=a_i$。

或者报告不存在合法解。

这里，$\oplus$ 代表按位异或运算，$\operatorname{popcount}(n)$ 表示非负整数 $n$ 二进制表示下 $1$ 的个数。

特别地，如果你正确地判断了解的存在性，也可以得到部分分，见【计分方式】。

输入格式

本题单个测试点内含有多组测试数据。

第一行，正整数 $T$，表示测试数据组数。

接下来描述 $T$ 组测试数据：

每组数据第一行，两个正整数 $n,k$。

每组数据第二行，$n$ 个非负整数 $a_1,a_2,\ldots,a_n$。

输出格式

对于每组数据，如果无解，输出一行一个 $\texttt{NO}$；

否则输出 $(n+1)$ 行，第一行输出 $\texttt{YES}$，接下来 $n$ 行，第 $i$ 行一个长度为 $k$ 的 $\texttt{01}$ 串，表示 $b_i$ 二进制表示下的低 $k$ 位。

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

YES
000
110
010
101
101
YES
000000
111000
111110
111111
000011
111011
011111
111111
000111
000001
NO

提示

数据范围

对于 $100\%$ 的数据，保证：

• $1\le T\le 10^5$；
• $2\le n$；
• $1\le k$；
• $2\le nk,\sum nk\le 5\times 10^6$；
• $0\le a_i\le k$。

• $\text{Subtask 0 (0 pts)}$：样例。
• $\text{Subtask 1 (5 pts)}$：$T,n,k\le 5$。
• $\text{Subtask 2 (2 pts)}$：$k=1$。
• $\text{Subtask 3 (8 pts)}$：$k=2$。
• $\text{Subtask 4 (32 pts)}$：$a_i\le k/2$。
• $\text{Subtask 5 (24 pts)}$：$n\le 5\times 10^4$，$k\le 20$。
• $\text{Subtask 6 (29 pts)}$：无额外约束。

计分方式

如果你正确地判断了解的存在性，但是构造的解不正确，你可以获得 $50\%$ 的分数。

如果你只想获得 $50\%$ 的分数，也要保证输出格式正确，否则将无法得分。

每个子任务的分数为其中每个测试点分数的最小值。