CF2085E Serval and Modulo

There is an array $ a $ consisting of $ n $ non-negative integers and a magic number $ k $ ( $ k\ge 1 $ , $ k $ is an integer). Serval has constructed another array $ b $ of length $ n $ , where $ b_i = a_i \bmod k $ holds $ ^{\text{∗}} $ for all $ 1\leq i\leq n $ . Then, he shuffled $ b $ . You are given the two arrays $ a $ and $ b $ . Find a possible magic number $ k $ . However, there is a small possibility that Serval fooled you, and such an integer does not exist. In this case, output $ -1 $ . It can be shown that, under the constraints of the problem, if such an integer $ k $ exists, then there exists a valid answer no more than $ 10^9 $ . And you need to guarantee that $ k\le 10^9 $ in your output. $ ^{\text{∗}} $ $ a_i \bmod k $ denotes the remainder from dividing $ a_i $ by $ k $ .

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\leq n\leq 10^4 $ ) — the length of the array $ a $ . The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0\leq a_i\leq 10^6 $ ) — the elements of the array $ a $ . The third line contains $ n $ integers $ b_1, b_2, \ldots, b_n $ ( $ 0\leq b_i\leq 10^6 $ ) — the elements of the array $ b $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^4 $ .

For each test case, output a single integer $ k $ ( $ 1\leq k\leq 10^9 $ ) — the magic number you found. Print $ -1 $ if it is impossible to find such an integer. If there are multiple answers, you may print any of them.

In the first test case, if $ k\ge 3 $ , then $ 2=a_3\bmod k $ should be in the array $ b $ , which leads to a contradiction. For $ k = 1 $ , $ [a_1\bmod k, a_2\bmod k, a_3\bmod k, a_4 \bmod k] = [0,0,0,0] $ , which cannot be shuffled to $ b $ . For $ k = 2 $ , $ [a_1\bmod k, a_2\bmod k, a_3\bmod k, a_4 \bmod k] = [1,1,0,1] $ , which can be shuffled to $ b $ . Thus, the only possible answer is $ k=2 $ . In the second test case, note that $ b $ can be obtained by shuffling $ a $ . Thus, all integers between $ 6 $ and $ 10^9 $ are possible answers. In the third test case, it can be shown that such $ k $ does not exist. Got fooled by Serval!