← 返回题目列表

Codeforces · 1482/B

B. 恢复模数

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

为了获得比赛第一名,Alex 赢得了许多整数数组,并确信这些数组非常昂贵。颁奖典礼结束后,亚历克斯决定卖掉它们。数组当铺有一条规则:只有可以压缩为生成器的数组才可以出售。

该生成器采用四个非负数 $$$n$$$、$$$m$$$、$$$c$$$、$$$s$$$。 $$$n$$$ 和 $$$m$$$ 必须为正,$$$s$$$ 非负,并且对于 $$$c$$$ 必须满足 $$$0 \leq c < m$$$。长度为 $$$n$$$ 的数组 $$$a$$$ 根据以下规则创建:

- $$$a_1 = s \bmod m$$$,这里$$$x \bmod y$$$表示$$$x$$$除以$$$y$$$的余数;
- $$$a_i = (a_{i-1} + c) \bmod m$$$ 对于所有 $$$i$$$ 使得 $$$1 < i \le n$$$。

例如,如果 $$$n = 5$$$、$$$m = 7$$$、$$$c = 4$$$ 且 $$$s = 10$$$,则 $$$a = [3, 0, 4, 1, 5]$$$。

此类数组的价格是该生成器中 $$$m$$$ 的值。

Alex 有一个问题:每个阵列他可以获得多少钱。请帮助他理解每个数组是否存在四个数字 $$$n$$$、$$$m$$$、$$$c$$$、$$$s$$$ 生成该数组。如果是,则最大化 $$$m$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 数组的数量。

数组描述的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 该数组的大小。

数组描述的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$ ) — 数组的元素。

保证数组大小之和不超过$$$10^5$$$。

输出

对于每个数组打印:

- $$$-1$$$,如果没有这四个数字生成这个数组;
- $$$0$$$,如果$$$m$$$可以任意大;
- 其他情况下的最大值 $$$m$$$ 和任何适当的 $$$c$$$ ($$$0 \leq c < m$$$)。

示例

输入 #1

6
6
1 9 17 6 14 3
3
4 2 2
3
7 3 4
3
2 2 4
5
0 1000000000 0 1000000000 0
2
1 1

输出 #1

19 8
-1
-1
-1
2000000000 1000000000
0