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

521 по-китайски звучит так же, как «I love you». В этот особенный день Little S хочет подарить Little A несколько хорошо подготовленных последовательностей, чтобы напомнить о своей дружбе, скреплённой на долгие годы.

Little S подготовил массив $$$a_1, a_2, \ldots, a_n$$$. Определим массив его префиксных сумм $$$b_1, b_2, \ldots, b_n$$$, где $$$b_i = a_1 + a_2 + \ldots + a_i$$$. Также определим массив префиксных максимумов для массива $$$b$$$: $$$c_1, c_2, \ldots, c_n$$$, где $$$c_i = \max(b_1, b_2, \ldots, b_i)$$$.

Теперь массив $$$a$$$ частично потерян, но, к счастью, у Little S всё ещё есть массив $$$c$$$. Ваша задача — восстановить массив $$$a$$$ и отправить его Little A, либо сообщить, что такого массива не существует — в этом случае добрая и милая Little A тоже не расстроится.

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

  • Если вы помните значение $$$a_i$$$, то $$$s_i = 1$$$, и вам дано истинное значение $$$a_i$$$.
  • Если вы не помните значение $$$a_i$$$, то $$$s_i = 0$$$, и вам дано $$$a_i = 0$$$.
Входные данные

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

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

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

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

Четвёртая строка каждого набора входных данных содержит $$$n$$$ чисел $$$c_1, c_2, \ldots, c_n$$$ ($$$|c_i| \le 2 \cdot 10^{11}$$$).

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

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

Для каждого набора входных данных в первой строке выведите «Yes», если массив $$$a$$$ существует, в противном случае выведите «No». Ответ вы можете выводить в любом регистре. Так, например, «YeS», «YES», «NO», «nO» будут также приняты.

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

Пример
Входные данные
10
4
1110
1 2 -1 0
1 3 3 3
5
00001
0 0 0 0 5
-4 -4 -1 -1 -1
1
1
0
1
6
001111
0 0 2 -3 3 -6
-5 -2 0 0 0 0
5
11110
1 2 0 5 0
1 2 2 7 6
2
01
0 1
-1 -1
6
001010
0 0 5 0 3 0
3 3 4 9 13 16
6
000100
0 0 0 4 0 0
2 6 6 7 7 7
2
00
0 0
4 -1
8
11111111
6 1 1 2 0 5 1 9
6 7 8 10 10 15 16 25
Выходные данные
Yes
1 2 -1 0
Yes
-4 0 3 -6 5
No
Yes
-5 3 2 -3 3 -6
No
No
No
Yes
2 4 -3 4 -100 0
No
Yes
6 1 1 2 0 5 1 9
Примечание

В первом наборе входных данных имеем:

  • $$$a = [1, 2, -1, 0]$$$.
  • $$$b = [1, 3, 2, 2]$$$.
  • $$$c = [1, 3, 3, 3]$$$.

В третьем наборе входных данных правильный массив $$$a$$$ должен быть равен $$$[1]$$$, поэтому решения не существует.