给定一个长度为 $$$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$$$。
示例
输入复制
741 4 41 2 3 444 0 41 1 1 1210 031 10 1 261 2 3 4 51 1 4 5 1 4200 040 1 0536870911 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$$$,这意味着不可能满足所有条件。