先考虑如何判断是否存在合法解。

由于所有限制都是关于两个数的相对关系的，所以我们可以假定 $b_1 = 0$，则是否存在合法解转化为是否存在一种方案满足前 $n - 1$ 条限制且 $\text{popcount}(b_n) = a_n$。

定义 $dp_{i, j}$ 表示是否存在一种方案使得满足前 $i - 1$ 条限制且 $\text{popcount}(b_i) = j$，考虑顺推，假设从第 $i$ 个数推到第 $i + 1$ 个数，枚举使 $b_i$ 中几个 $1$ 变为 $0$，则可以表示出其能转移到的下一个状态，复杂度 $O(nk^2)$。

dp[1][0] = 1;
for (int i = 1; i < n; i++){
	for (int j = 0; j <= k; j++)
		if (dp[i][j])
			for (int x = max(0, a[i] - k + j); x <= min(j, a[i]); x++)
				dp[i + 1][j - x + a[i] - x] = 1;
}

考虑优化，我们发现每次转移到的位置都是编号奇偶性相同的一段连续段，于是我们可以对编号为奇数和编号为偶数的位置分别建立差分数组，每次转移可以看成区间覆盖，这样可以做到 $O(nk)$。

dp[1][0] = 1;
for (int i = 1; i < n; i++){
	for (int j = 0; j <= k; j++)
		if (dp[i][j]){
			int l = abs(a[i] - j), r = min(a[i] + j, k * 2 - a[i] - j);
			if (l <= r){
				dp[i + 1][l]++;
				if (r + 2 <= k)		dp[i + 1][r + 2]--;
			}
		}
	for (int j = 2; j <= k; j += 2)	dp[i + 1][j] += dp[i + 1][j - 2];
	for (int j = 3; j <= k; j += 2)	dp[i + 1][j] += dp[i + 1][j - 2];
}

考虑如何找出合法解，我们把 dp 的过程倒过来，回溯找出一种合法的方案，由于根据上一个 dp 状态可以推出分别改了几个 $0$，几个 $1$，所以可以很简单地找出合法解，复杂度 $O(nk)$。

总复杂度 $O(nk)$，略微有点卡空间，实现的时候要注意一下。

code。

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N = 5e6 + 10;
int T, n, k, a[N];
vector<int> ans, dp[N];

void dfs(int x, int y){
	if (x == 1){
		ans.resize(k, 0);
		for (auto x : ans)	cout << x;
		cout << endl;
		return;
	}
	for (int j = 0; j <= k; j++)
		if (dp[x - 1][j]){
			int l = abs(a[x - 1] - j), r = min(a[x - 1] + j, k * 2 - a[x - 1] - j);
			if ((l & 1) == (y & 1) && l <= y && y <= r){
				dfs(x - 1, j);
				int chg0 = (a[x - 1] + y - j) / 2, chg1 = a[x - 1] - chg0;
				vector<int> pos0, pos1;
				for (int i = 0; i < k; i++)
					!ans[i] ? pos0.push_back(i) : pos1.push_back(i);
				for (int i = 0; i < chg0; i++)	ans[pos0[i]] = 1;
				for (int i = 0; i < chg1; i++)	ans[pos1[i]] = 0;
				for (auto x : ans)	cout << x;
				cout << endl;
				return;
			}
		}
}

void Solve(){
	cin >> n >> k;
	for (int i = 1; i <= n; i++)	cin >> a[i];
	for (int i = 1; i <= n; i++)	dp[i].resize(k + 1, 0);
	dp[1][0] = 1;
	for (int i = 1; i < n; i++){
		for (int j = 0; j <= k; j++)
			if (dp[i][j]){
				int l = abs(a[i] - j), r = min(a[i] + j, k * 2 - a[i] - j);
				if (l <= r){
					dp[i + 1][l]++;
					if (r + 2 <= k)		dp[i + 1][r + 2]--;
				}
			}
		for (int j = 2; j <= k; j += 2)	dp[i + 1][j] += dp[i + 1][j - 2];
		for (int j = 3; j <= k; j += 2)	dp[i + 1][j] += dp[i + 1][j - 2];
	}
	if (dp[n][a[n]]){
		cout << "YES\n" ;
		ans.clear(), dfs(n, a[n]);
	}else	cout << "NO\n" ;
	for (int i = 1; i <= n; i++)	dp[i].clear();
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> T;
	while (T --> 0)		Solve();
	return 0;
}