题目描述

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

Aquawave 想要构造一个长度为 $n$ 的排列 $p$，使得对于所有 $1 \le i \le n$ 且 $s_i = \mathtt{1}$ 的下标 $i$，满足如下条件：

• 对于每一个长度不少于 $k$ 的区间 $[l, r]$（即 $r - l + 1 \geq k$）且覆盖位置 $i$（即 $l \leq i \leq r$），该区间内的最大元素 $p_l, p_{l+1}, \ldots, p_r$ 中，最大值不能等于 $p_i$。

注意，对于 $s_i = \mathtt{0}$ 的下标 $i$ 没有上述限制。

请你找出这样一个排列，或者判断不存在这样的排列。

$^{\text{∗}}$ 二进制字符串指的是每个字符都是 $\mathtt{0}$ 或 $\mathtt{1}$ 的字符串。

$^{\text{†}}$ 长度为 $n$ 的排列是一个由 $n$ 个互不相同的 $1$ 到 $n$ 的整数构成的数组，例如 $[2,3,1,5,4]$ 是一个排列，而 $[1,2,2]$ 不是排列（$2$ 出现了两次），$[1,3,4]$ 也不是排列（长度为 $3$，但出现了 $4$）。

输入格式

每组测试数据包含多组测试用例。第一行输入一个整数 $t$（$1 \le t \le 10^4$），表示测试用例数量。

每个测试用例的第一行输入两个整数 $n$ 和 $k$（$1 \leq n \leq 2 \cdot 10^5$，$1 \leq k \leq n$），分别表示字符串 $s$ 的长度和给定的整数。

第二行输入一个长度为 $n$ 的二进制字符串 $s$（$s_i = \mathtt{0}$ 或 $\mathtt{1}$）。

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

输出格式

对于每组测试用例：

• 如果存在至少一个满足条件的排列，请：
  • 在第一行输出 YES（大小写均可）；
  • 在第二行输出 $n$ 个两两不同的整数 $p_1, p_2, \ldots, p_n$（$1 \leq p_i \leq n$），即你构造的排列。
• 否则输出 NO。

如果存在多组解，输出任意一组均可。

说明/提示

在第一个测试用例中，你可以输出任意长度为 $n = 2$ 的排列，因为所有 $s_i$ 都等于 $\mathtt{0}$。

在第二个测试用例中，$p=[1, 4, 3, 2]$ 是一个合法解，因为：

• 唯一一个 $s_i = \mathtt{1}$ 的位置是 $i = 3$，覆盖 $3$ 且长度不少于 $k=3$ 的区间共有三个，分别为 $[1, 3]$，$[1, 4]$ 和 $[2, 4]$；
• 对于这三个区间，每个区间的最大值都是 $p_2 = 4$，显然最大值不等于 $p_3 = 3$。

由 ChatGPT 5 翻译

样例

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