给你一个长度为$$$n$$$的二进制字符串$$$^{\text{*}}$$$ $$$s$$$,以及一个整数$$$k$$$。
Aquawave 想要构造一个长度为 $$$n$$$ 的排列$$$^{\text{†}}$$$ $$$p$$$,因此对于每个 $$$1\le i\le n$$$,其中 $$$s_i=\mathtt{1}$$$,以下成立:
- 对于每个长度至少为$$$k$$$(即$$$r - l + 1 \geq k$$$)的区间$$$[l, r]$$$ ($$$1\le l\le r\le n$$$),如果它覆盖位置$$$i$$$(即$$$l \leq i \leq r$$$),则其中的最大元素$$$p_l, p_{l+1}, \ldots, p_r$$$ 是 不 $$$p_i$$$。
请注意,有 no 对 $$$s_i = \mathtt{0}$$$ 的索引的此类约束。
你必须找到这样的排列,或者确定这样的排列不存在。
$$$^{\text{*}}$$$二进制字符串是每个字符为 $$$\mathtt{0}$$$ 或 $$$\mathtt{1}$$$ 的字符串。
$$$^{\text{†}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=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$$$。
输出
对于每个测试用例:
- 如果至少存在一种可能的排列:
- 打印“是"在输出的第一行;
- 然后,在第二行打印 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$, 所有 $$$p_i$$$-s 都是不同的) — 您构建的排列。
- 否则,打印“NO”在单行输出中。
您可以在任何情况下输出令牌(上限或下限)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。
如果有多个答案,您可以输出其中任何一个。
示例
输入复制
62 1004 300105 2110117 511111108 40010101110 21000000010
输出复制
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
注意
在第一个测试用例中,您可以输出长度 $$$n = 2$$$ 的任意排列,因为所有 $$$s_i$$$-s 都等于 $$$\mathtt{0}$$$。
在第二个测试用例中, $$$p=[1, 4, 3, 2]$$$ 是有效答案,因为:
- $$$s_i = \tt{1}$$$ 的唯一位置是 $$$i = 3$$$。存在三个不同的区间 $$$[l, r]$$$ 覆盖索引 $$$3$$$,其长度至少为 $$$k=3$$$:$$$[1, 3]$$$、$$$[1, 4]$$$ 和 $$$[2, 4]$$$;
- 并且,对于三个区间中的每一个,$$$p_l, \ldots, p_r$$$ 中的最大元素应该是 $$$p_2 = 4$$$,它不等于 $$$p_3 = 3$$$。