为了获得比赛第一名,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