题目描述

数组 $a$ 的前缀和定义为：

再定义：

现在给出完整的数组 $c$，以及数组 $a$ 中的一部分已知值。请恢复任意一个满足条件的数组 $a$，或判断不存在。

输入格式

每个测试包含多组测试数据。

第一行包含整数 $t$（$1 \le t \le 10^4$）。

每组测试数据第一行包含整数 $n$（$1 \le n \le 2\cdot 10^5$）。

第二行包含长度为 $n$ 的二进制串 $s$。

第三行包含 $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$。

输出格式

对于每组测试数据，若存在合法数组 $a$，第一行输出 Yes；否则输出 No。大小写任意。

若存在解，第二行输出 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$|a_i| \le 10^{18}$）。若有多组解，输出任意一组。

样例 1

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

约束与提示

• 时间限制：2 秒

• 内存限制：256 MB

• 原题编号：CF2231D