E. Range Modulo Queries
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Raman is a curious kid who likes to play with arrays. One day, his friend Pradeep, a math nerd came to meet him. He gave Raman two arrays $$$a$$$ $$$(a_1,a_2,a_3,...,a_n)$$$ and $$$b$$$ $$$(b_1,b_2,b_3,...,b_n)$$$, both of size $$$n$$$, and asked this problem:

"Given $$$q$$$ queries of the form: $$$l$$$ $$$r$$$ , where $$$1\le l \le r \le n$$$ .

Find minimum possible positive integer $$$m$$$ such that $$$a_i \bmod m = b_i$$$ for all $$$l \le i \le r$$$. And, if no such $$$m$$$ exists, then print $$$-1$$$."

Raman finds the problem difficult to solve,and hence asks you for help. Please solve this problem for him.

Input

The first line contains an integer $$$t (1 \le t \le 10^5)$$$ - the number of test cases.

The descriptions of the test cases follow.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ $$$(1 \le n,q \le 10^6)$$$ - the size of the array and the number of queries.

The second line contains $$$n$$$ space-separated non-negative integers $$$a_1, a_2, a_3, ..., a_n$$$ $$$(0 \le a_i \le 10^6)$$$ — the elements of array $$$a$$$.

The third line contains $$$n$$$ space-separated non-negative integers $$$b_1, b_2, b_3, ..., b_n$$$ $$$(0 \le b_i \le 10^6)$$$ — the elements of array $$$b$$$.

The next $$$q$$$ lines contain the queries: $$$l$$$ $$$r$$$ $$$(1 \le l \le r \le n)$$$.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases do not exceed $$$10^6$$$.

Output

For each query, output a single positive integer $$$m$$$, as required.

If no such $$$m$$$ exists, then print $$$-1$$$ for that query.

Example
Input
1
4 5
0 18 31 17
1 2 7 5
1 1
2 2
2 3
3 4
2 4
Output
-1
4
8
12
-1