有一个数组$$$a$$$,由$$$n$$$非负整数和a组成 幻数 $$$k$$$ ($$$k\ge 1$$$,$$$k$$$ 是一个整数)。 Serval 构造了另一个长度为 $$$n$$$ 的数组 $$$b$$$,其中 $$$b_i = a_i \bmod k$$$ 为所有 $$$1\leq i\leq n$$$ 保存了$$$^{\text{*}}$$$。然后,他 已洗牌 $$$b$$$。
给定两个数组 $$$a$$$ 和 $$$b$$$。寻找一个可能的 幻数 $$$k$$$。不过,有很小的可能是Serval欺骗了你,这样的整数并不存在。在这种情况下,输出$$$-1$$$。
可以证明,在问题的约束下,如果存在这样一个整数$$$k$$$,则存在不超过$$$10^9$$$的有效答案。并且您需要保证输出中有 $$$k\le 10^9$$$ 。
$$$^{\text{*}}$$$$$$a_i \bmod k$$$ 表示 $$$a_i$$$ 除以 $$$k$$$ 所得的余数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\leq n\leq 10^4$$$) — 数组 $$$a$$$ 的长度。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0\leq a_i\leq 10^6$$$) — 数组 $$$a$$$ 的元素。
第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$0\leq b_i\leq 10^6$$$) — 数组 $$$b$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^4$$$。
输出
对于每个测试用例,输出一个整数 $$$k$$$ ($$$1\leq k\leq 10^9$$$) — 幻数 你发现了。如果无法找到这样的整数,则打印 $$$-1$$$。
如果有多个答案,您可以打印其中任何一个。
示例
输入复制
543 5 2 70 1 1 153 1 5 2 41 2 3 4 562 3 4 7 8 91 2 3 6 7 8521 22 25 28 200 1 2 1 061 1 2 3 5 80 0 1 1 0 0
输出复制
2 31415926 -1 4 -1
注意
在第一个测试用例中,如果$$$k\ge 3$$$,那么$$$2=a_3\bmod k$$$应该在数组$$$b$$$中,这导致了矛盾。对于$$$k = 1$$$,$$$[a_1\bmod k, a_2\bmod k, a_3\bmod k, a_4 \bmod k] = [0,0,0,0]$$$,不能被打乱到$$$b$$$。对于$$$k = 2$$$,$$$[a_1\bmod k, a_2\bmod k, a_3\bmod k, a_4 \bmod k] = [1,1,0,1]$$$,可以将其打乱为$$$b$$$。因此,唯一可能的答案是$$$k=2$$$。
在第二个测试用例中,请注意 $$$b$$$ 可以通过对 $$$a$$$ 进行混洗来获得。因此,$$$6$$$ 和 $$$10^9$$$ 之间的所有整数都是可能的答案。
在第三个测试用例中,可以证明这样的$$$k$$$不存在。被薮猫骗了!