Range Modulo Queries
本题没有可用的提交语言。
Description
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.
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$.
For each query, output a single positive integer $m$, as required.
If no such $m$ exists, then print $-1$ for that query.
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.
1
4 5
0 18 31 17
1 2 7 5
1 1
2 2
2 3
3 4
2 4
-1
4
8
12
-1