题目描述

题目译自 Romanian Master of Informatics 2024 Day2 T1 「Signals」

布加勒斯特国际计算机学院有一套由 $N$ 台计算机组成的环形网络。每台计算机都按顺序连接成一个圈：第 $i$ $(1 \leq i < N)$ 台计算机通过链接 $i$ 与第 $i + 1$ 台相连，而第 $N$ 台和第 $1$ 台通过链接 $N$ 连接。

每台计算机有一个由 $K$ 位信息组成的密钥，用长度为 $K$ 的二进制字符串表示。每个链接 $i$ 还有一个安全阈值 $W_i$。通过这个链接连接的两台计算机只有在它们的密钥恰好在 $W_i$ 个位上不同时才能通信。

系统管理员不小心丢失了所有密钥，现在需要你的帮助重新生成一组密钥，确保每条链接都能支持通信。

输入格式

输入的第一行包含一个整数 $T$，表示需要解决的测试数据组数。接下来是 $T$ 组测试数据的描述。

每组测试数据的第一行包含两个空格分隔的整数 $N$ 和 $K$。第二行包含 $N$ 个空格分隔的整数 $W_1, W_2, \dots, W_N$，表示各链接的安全阈值。

输出格式

依次输出 $T$ 组测试数据的答案。每组测试数据的答案格式如下：

如果某组测试数据无解，输出一行 NO。否则，第一行输出 YES，接下来的第 $2$ 到 $N + 1$ 行输出一组有效的密钥。每台计算机 $i$ 的密钥在第 $(i + 1)$ 行输出为一个无空格的二进制字符串。

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

对于第一组测试数据，密钥 000 和 110 在 $2$ 个位上不同，110 和 010 在 $1$ 个位上不同，010 和 101 在 $3$ 个位上不同，101 和 101 在 $0$ 个位上不同，101 和 000 在 $2$ 个位上不同，满足所有五个安全阈值。

对于第二组测试数据，无法找到一组密钥满足所有条件，因此输出 NO。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq T \leq 100 \ 000$
• $2 \leq N$
• $2 \leq N \cdot K \leq 5 \ 000 \ 000$
• $0 \leq W_i \leq K$
• 保证所有测试数据中 $N \cdot K$ 的总和不超过 $5 \ 000 \ 000$。
• 如果你能正确判断是否存在解，但输出的密钥不正确（格式正确），仍可获得该子任务 $50\%$ 的分数。
• 设 $W_{max}$ 为所有 $W_i$ 中的最大值。

详细子任务附加限制及分值如下表所示。