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

521 在中文中与 “I love you” 谐音。在这个特别的日子里，小 S 想要送给小 A 一些精心准备的数列，以唤起他们多年以来牢不可破的友谊。

小 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$ 已部分丢失，但幸运的是，小 S 仍保留着数组 $c$。你的任务是根据 $c$ 恢复出原数组 $a$ 并将其发送给小 A；若不存在满足条件的数组，则报告无解——此时善良又可爱的小 A 也不会生气哦。

形式化地，你将获得一个二进制字符串 $s$、一个部分填充的数组 $a$ 以及一个数组 $c$，满足：

• 若你记得 $a_i$ 的值，则 $s_i = 1$，且你被给出真实的 $a_i$ 值；
• 若你不记得 $a_i$ 的值，则 $s_i = 0$，且你被给出 $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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。

每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$（其中 $s_i \in \{\texttt{0}, \texttt{1}\}$）。

每个测试用例的第三行包含 $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$。

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.

对于每个测试用例，如果数组 $a$ 存在，则在第一行输出 "Yes"；否则输出 "No"。你可以以任意大小写形式输出答案，例如 "YeS"、"YES"、"NO"、"nO" 均可接受。

如果至少存在一个解，则在第二行输出 $n$ 个整数 $a_1, a_2, \ldots, a_n$（满足 $|a_i| \leq 10^{18}$）。如果存在多个合适的数组，你可以输出其中任意一个。

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.

在第一个测试用例中，我们有：

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

在第三个测试用例中，正确的数组 $a$ 应等于 $[1]$，因此不存在解。