题目描述

给定一个长度为 $n$ 的二进制字符串 $s$，以及一个整数 $k$。

你需要构造一个长度为 $n$ 的排列 $p$，满足：对于每个满足 $s_i=1$ 的位置 $i$（$1 \le i \le n$），以下条件必须成立：

对于每一个长度至少为 $k$（即 $r-l+1 \ge k$）且包含位置 $i$（即 $l \le i \le r$）的区间 $[l,r]$（$1 \le l \le r \le n$），区间内的最大值不能是 $p_i$。

对于 $s_i=0$ 的位置，没有任何限制。

请你构造出满足条件的排列，或者判断不存在这样的排列。

名词解释

• 二进制字符串：仅由字符 $0$ 和 $1$ 组成的字符串。
• 排列：长度为 $n$ 的排列是一个由 $1 \sim n$ 这 $n$ 个互不相同的整数组成的数组。

输入格式

每个测试点包含多组测试数据。 第一行输入测试数据组数 $t$（$1 \le t \le 10^4$）。

每组测试数据： 第一行输入两个整数 $n, k$（$1 \le n \le 2 \cdot 10^5$，$1 \le k \le n$）。 第二行输入长度为 $n$ 的二进制字符串 $s$。

保证所有测试数据的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每组测试数据：

• 如果存在合法排列： 第一行输出 YES； 第二行输出 $n$ 个整数 $p_1,p_2,\dots,p_n$（$1 \le p_i \le n$，所有数字互不相同）。
• 否则，仅输出一行 NO。

你可以以任意大小写形式输出 YES/NO。 如果存在多个答案，输出任意一个合法答案即可。

样例输入

6
2 1
00
4 3
0010
5 2
11011
7 5
1111110
8 4
00101011
10 2
1000000010

样例输出

YES
1 2
YES
1 4 3 2
NO
NO
YES
6 5 2 3 4 8 1 7
YES
1 2 3 4 5 6 7 9 8 10

样例解释

• 第一组测试数据：所有 $s_i=0$，无任何限制，输出任意排列均可。
• 第二组测试数据：唯一的 $s_i=1$ 位置是 $i=3$。所有长度 $\ge 3$ 且包含 $3$ 的区间最大值都不是 $p_3$，因此合法。