周期函数

题号：NC288080
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 二维坐标平面上有 $n$ 个整数点，它们的坐标通过整数数组 $\{x_1,x_2,\dots,x_n\}$ 和整数数组 $\{y_1,y_2,\dots,y_n\}$ 来定义，第 $i$ 个点的坐标为 $(x_i,y_i)$ 。特别地，我们还保证，数组 $x$ 满足 $x_1 < x_2 < \dots < x_n$ 。
$\hspace{15pt}$ 对于每一组相邻点对 $(x_i,y_i)$ 和 $(x_{i+1},y_{i+1}) \left( 1 \leq i \lt n \right)$ ，用线段连接这两个点，得到定义域为 $[x_1,x_n]$ 的分段线性函数 $f(x)$ 。例如，在下图中，给定的六个整数点 $(-3,1)$ 、 $(-2,2)$ 、 $(0,1)$ 、 $(1,2)$ 、 $(3,1)$ 、 $(4,0)$ 生成的函数 $f(x)$ 在定义域 $[-3,4]$ 上的图像如下图所示：
周期函数

$\hspace{15pt}$ 定义函数 $f(x)$ 在区间 $[l,r]$ 上的最小周期为满足以下条件的最小正整数 $t$ ：
$\hspace{23pt}\bullet\,$ $0 \pmb{\lt} t \pmb{\lt} r - l$ （注意此处的符号）；

$\hspace{23pt}\bullet\,$ 对于任意的 $x$ 满足 $l \leq x \leq r - t$ ，都有 $f(x) = f(x + t)$ 。

$\hspace{23pt}\bullet\,$ 存在一个正整数 $k$ ，使得 $r - l = kt$ 。

$\hspace{15pt}$ 特别地，若不存在这样的 $t$ ，则将其定义为 $-1$ 。

$\hspace{15pt}$ 现在，进行 $q$ 次询问，每次给定区间 $[l, r]$ ，求该区间上的最小周期 $t$ 。

输入描述:

第一行输入两个正整数  代表平面上整点的个数、查询次数。
第二行输入  个整数  代表整点的横坐标。 
第三行输入  个整数  代表整点的纵坐标。 
此后  行，每行输入两个整数  代表函数在区间  上的最小周期。保证 ，。且不存在  ，使得  。

输出描述:

对于每一次询问，新起一行。输出一个正整数，代表函数在询问区间上的最小周期。

示例1

输入

复制

6 3
-3 -2 0 1 3 4
1 2 1 2 1 0
-3 3
-3 4
1 1

输出

复制

3
-1
-1

说明

在这个样例中，函数的图像已经在题面中给出。

示例2

输入

复制

输出

复制

说明

该函数图像是一条以  和  为端点的与  轴平行的线段，由于最小周期只能是正整数，因此为  。

示例3

输入

复制

输出

复制

-1

说明

该函数图像是一条以  和  为端点的与  轴平行的线段，由于最小周期只能是正整数且小于 ，因此为  。

备注:

在几乎全部的情况下，PyPy 的运行速度优于 Python，我们建议您选择对应版本的 PyPy 进行提交、而不是 Python。
        此外，请注意本题特别的时间限制。