← 返回题目列表

Codeforces · 2050/F

F. 最大模数相等

中文机器翻译题面 查看原题

给定一个长度为 $$$n$$$ 的数组 $$$a$$$ 和 $$$q$$$ 查询 $$$l$$$、$$$r$$$。

对于每个查询,找到最大可能的 $$$m$$$,使得所有元素 $$$a_l$$$、$$$a_{l+1}$$$、...、$$$a_r$$$ 都等于模 $$$m$$$。换句话说,$$$a_l \bmod m = a_{l+1} \bmod m = \dots = a_r \bmod m$$$,其中 $$$a \bmod b$$$ - 是 $$$a$$$ 除以 $$$b$$$ 的余数。特别是,当 $$$m$$$ 可以是无限时,打印 $$$0$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$、$$$q$$$ ($$$1 \le n, q \le 2\cdot 10^5$$$) - 数组的长度和查询的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — 数组的元素。

在每个测试用例的以下 $$$q$$$ 行中,提供了两个整数 $$$l$$$、$$$r$$$ ($$$1 \le l \le r \le n$$$) - 查询的范围。

保证所有测试用例的$$$n$$$总和不超过$$$2\cdot 10^5$$$,并且$$$q$$$总和不超过$$$2\cdot 10^5$$$。

输出

对于每个查询,输出语句中描述的最大值$$$m$$$。

示例

输入 #1

3
5 5
5 14 2 6 3
4 5
1 4
2 4
3 5
1 1
1 1
7
1 1
3 2
1 7 8
2 3
1 2

输出 #1

3 1 4 1 0 
0 
1 6

注意

在第一个样本的第一个查询中,$$$6 \bmod 3 = 3 \bmod 3 = 0$$$。可以证明,对于更大的$$$m$$$,将无法满足所需的条件。

在第一个样本的第三个查询中,$$$14 \bmod 4 = 2 \bmod 4 = 6 \bmod 4 = 2$$$。可以证明,对于更大的$$$m$$$,将无法满足所需的条件。