C. Максимальная сумма подмассива
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a_1,a_2,\ldots,a_n$$$ длины $$$n$$$ и положительное целое число $$$k$$$, но некоторые части массива $$$a$$$ отсутствуют. Ваша задача — заполнить недостающую часть так, чтобы максимальная сумма подмассива$$$^{\text{∗}}$$$ массива $$$a$$$ была равна $$$k$$$, или сообщить, что решения не существует.

Формально, вам дана бинарная строка $$$s$$$ и частично заполненный массив $$$a$$$, где:

  • Если вы помните значение $$$a_i$$$, то это обозначается как $$$s_i = 1$$$, и вам дано реальное значение $$$a_i$$$.
  • Если вы не помните значение $$$a_i$$$, то это обозначается $$$s_i = 0$$$, и вам дано $$$a_i = 0$$$.

Все значения, которые вы помните, удовлетворяют $$$|a_i| \le 10^6$$$. Однако вы можете использовать значения до $$$10^{18}$$$, чтобы заполнить значения, которые вы не помните. Можно доказать, что если решение существует, то также существует решение, удовлетворяющее $$$|a_i| \le 10^{18}$$$.

$$$^{\text{∗}}$$$ Максимальная сумма подмассива массива $$$a$$$ длины $$$n$$$, т.е. $$$a_1, a_2, \ldots a_n$$$, определяется как $$$\max_{1 \le i \le j \le n} S(i, j)$$$, где $$$S(i, j) = a_i + a_{i + 1} + \ldots + a_j$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два числа $$$n,k$$$ ($$$1 \le n \le 2 \cdot 10^5,1 \le k \le 10^{12}$$$).

Вторая строка каждого набора входных данных содержит бинарную ($$$\texttt{01}$$$) строку $$$s$$$ длины $$$n$$$.

Третья строка каждого набора входных данных содержит $$$n$$$ чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$|a_i| \le 10^6$$$). Если $$$s_i = \texttt{0}$$$, то гарантируется, что $$$a_i = 0$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных сначала выведите $$$\texttt{Yes}$$$, если решение существует, или $$$\texttt{No}$$$, если решения не существует. Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки $$$\texttt{YES}$$$ и $$$\texttt{yEs}$$$ будут приняты как положительный ответ.

Если существует хотя бы одно решение, выведите $$$n$$$ чисел $$$a_1,a_2,\ldots,a_n$$$ на второй строке. Должно выполняться условие $$$|a_i| \le 10^{18}$$$.

Пример
Входные данные
10
3 5
011
0 0 1
5 6
11011
4 -3 0 -2 1
4 4
0011
0 0 -4 -5
6 12
110111
1 2 0 5 -1 9
5 19
00000
0 0 0 0 0
5 19
11001
-8 6 0 0 -5
5 10
10101
10 0 10 0 10
1 1
1
0
3 5
111
3 -1 3
4 5
1011
-2 0 1 -5
Выходные данные
Yes
4 0 1
Yes
4 -3 5 -2 1
Yes
2 2 -4 -5
No
Yes
5 1 9 2 2
Yes
-8 6 6 7 -5
Yes
10 -20 10 -20 10
No
Yes
3 -1 3
Yes
-2 4 1 -5
Примечание

В $$$1$$$ наборе входных данных только первая позиция не заполнена. Мы можем заполнить её $$$4$$$, чтобы получить массив $$$[4, 0, 1]$$$, который имеет максимальную сумму подмассива $$$5$$$.

В $$$2$$$ наборе входных данных только третья позиция не заполнена. Мы можем заполнить её $$$5$$$, чтобы получить массив $$$[4, -3, 5, -2, 1]$$$. Здесь максимальная сумма подмассива получается из подмассива $$$[4, -3, 5]$$$, и она равна $$$6$$$, как и требуется.

В $$$3$$$ наборе входных данных первая и вторая позиции не заполнены. Мы можем заполнить обе позиции $$$2$$$, чтобы получить массив $$$[2, 2, -4, -5]$$$, который имеет максимальную сумму подмассива $$$4$$$. Обратите внимание, что также возможны и другие ответы, например $$$[0, 4, -4, -5]$$$.

В $$$4$$$ наборе входных данных невозможно получить допустимый массив. Например, если мы заполним третью позицию $$$0$$$, мы получим $$$[1, 2, 0, 5, -1, 9]$$$, но он имеет максимальную сумму подмассива $$$16$$$, а не $$$12$$$, как требуется.