← 返回题目列表

Codeforces · 2119/E

E. 和约束

中文机器翻译题面 查看原题
wowaka & 初音未来 - Tosenbo

给定一个长度为 $$$n-1$$$ 的序列 $$$a$$$ 和一个长度为 $$$n$$$ 的序列 $$$b$$$。

您可以执行以下操作任意次数(可能为零):

  • 选择索引 $$$1 \le i \le n$$$ 并将 $$$b_i$$$ 增加 $$$1$$$ (即设置 $$$b_i \leftarrow b_i + 1$$$)。

您的目标是执行 最小操作次数 使得对于每个$$$1 \le i \le n-1$$$,条件$$$b_i \, \& \, b_{i+1} = a_i$$$成立,其中$$$\&$$$表示按位AND运算。如果无法满足条件,也应报告。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$)。

第二行包含 $$$n-1$$$ 整数 $$$a_1, a_2, \ldots, a_{n-1}$$$ ($$$0 \le a_i \lt 2^{29}$$$)。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \lt 2^{29}$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,您只需要输出一个整数。

如果目标可以实现,则输出一个整数——所需的最少操作数。否则,输出$$$-1$$$。

示例

输入
复制

7
4
1 4 4
1 2 3 4
4
4 0 4
1 1 1 1
2
1
0 0
3
1 1
0 1 2
6
1 2 3 4 5
1 1 4 5 1 4
2
0
0 0
4
0 1 0
536870911 536870911 536870911 536870911

输出
复制

4
-1
2
2
-1
0
536870916

注意

在第一个测试用例中,最佳策略之一是使用 $$$4$$$ 运算使 $$$b = [1,5,4,4]$$$,满足所有条件。我们可以证明不可能使用少于 $$$4$$$ 的操作。

在第二个测试用例中,由于 $$$b_1 \, \& \, b_2 = 4$$$ 且 $$$b_2 \, \& \, b_3 =0$$$,则 $$$b_3 \, \& \, 4 =0$$$。但是,我们要求$$$b_3 \, \& \, b_4 =4$$$,这意味着不可能满足所有条件。