D. Maximum Prefix Sums
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

521 sounds the same as "I love you" in Chinese. On this special day, Little S wants to give Little A some well-prepared sequences to recall their friendship sealed for years.

Little S has prepared an array $$$a_1, a_2, \ldots, a_n$$$. Let's define its prefix sums array $$$b_1, b_2, \ldots, b_n$$$, where $$$b_i = a_1 + a_2 + \ldots + a_i$$$. Also define the prefix maximum array of $$$b$$$: $$$c_1, c_2, \ldots, c_n$$$, where $$$c_i = \max(b_1, b_2, \ldots, b_i)$$$.

Now array $$$a$$$ has been partially lost, but luckily Little S still keeps the array $$$c$$$. Your task is to restore the array $$$a$$$ and send it to Little A, or report that no such array exists — in this case, the kind and cute Little A won't get mad either.

Formally, you are given a binary string $$$s$$$, a partially filled array $$$a$$$, and an array $$$c$$$, where:

  • If you remember the value of $$$a_i$$$, then $$$s_i = 1$$$, and you are given the true value of $$$a_i$$$.
  • If you do not remember the value of $$$a_i$$$, then $$$s_i = 0$$$, and you are given $$$a_i = 0$$$.
Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

The second line of each test case contains a binary string $$$s$$$ ($$$s_i \in \{\texttt{0}, \texttt{1}\}$$$) of length $$$n$$$.

The third line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$|a_i| \le 10^6$$$). If $$$s_i = \texttt{0}$$$, then it is guaranteed that $$$a_i = 0$$$.

The fourth line of each test case contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$|c_i| \le 2 \cdot 10^{11}$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print "Yes" in the first line if the array $$$a$$$ exists, otherwise print "No". You may print the answer in any case. For example, "YeS", "YES", "NO", "nO" will also be accepted.

If there is at least one solution, print $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$|a_i| \leq 10^{18}$$$) in the second line. If there are multiple suitable arrays, you may print any of them.

Example
Input
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
Output
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
Note

In the first test case, we have:

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

In the third test case, the correct array $$$a$$$ should be equal to $$$[1]$$$, so no solution exists.