Statement : D. Maximum Prefix Sums

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$.

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$.

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.

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.