B. Как битсет
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана бинарная строка$$$^{\text{∗}}$$$ $$$s$$$ длиной $$$n$$$, а также целое число $$$k$$$.

Аквавейв хочет построить перестановку$$$^{\text{†}}$$$ $$$p$$$ длиной $$$n$$$, так чтобы для каждого $$$1\le i\le n$$$, где $$$s_i=\mathtt{1}$$$, выполнялось следующее:

  • Для каждого интервала $$$[l, r]$$$ ($$$1\le l\le r\le n$$$), длина которого не менее $$$k$$$ (т.е. $$$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}$$$.

Вам нужно найти такую перестановку или определить, что её не существует.

$$$^{\text{∗}}$$$Бинарная строка — это строка, в которой каждый символ является либо $$$\mathtt{0}$$$, либо $$$\mathtt{1}$$$.

$$$^{\text{†}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$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$$$ и целое число из условия.

Вторая строка содержит бинарную строку $$$s$$$ длиной $$$n$$$ ($$$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$$$, все $$$p_i$$$ различны) во второй строке — перестановку, которую вы построили.
  • В противном случае выведите «NO» в единственной строке вывода.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Если существует несколько возможных ответов, вы можете вывести любой из них.

Пример
Входные данные
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
Примечание

В первом наборе входных данных вы можете вывести произвольную перестановку длины $$$n = 2$$$, так как все $$$s_i$$$ равны $$$\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$$$.