TheForces Round #25(5^2-Forces) |
---|
Finished |
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.
14 50 18 31 171 2 7 51 12 22 33 42 4
-1 4 8 12 -1
Name |
---|