CF1484B.Restore Modulo

For the first place at the competition, Alex won many arrays of integers and was assured that these arrays are very expensive. After the award ceremony Alex decided to sell them. There is a rule in arrays pawnshop: you can sell array only if it can be compressed to a generator.

This generator takes four non-negative numbers $n$, $m$, $c$, $s$. $n$ and $m$ must be positive, $s$ non-negative and for $c$ it must be true that $0 \leq c \lt m$. The array $a$ of length $n$ is created according to the following rules:

• $a_1 = s \bmod m$, here $x \bmod y$ denotes remainder of the division of $x$ by $y$;
• $a_i = (a_{i-1} + c) \bmod m$ for all $i$ such that $1 \lt i \le n$.

For example, if $n = 5$, $m = 7$, $c = 4$, and $s = 10$, then $a = [3, 0, 4, 1, 5]$.

Price of such an array is the value of $m$ in this generator.

Alex has a question: how much money he can get for each of the arrays. Please, help him to understand for every array whether there exist four numbers $n$, $m$, $c$, $s$ that generate this array. If yes, then maximize $m$.

在比赛第一名的奖品中，亚历克斯赢得了许多整数数组，并被告知这些数组非常昂贵。颁奖仪式结束后，亚历克斯决定出售它们。数组当铺有一条规则：只有当一个数组可以被压缩为某个生成器时，才能出售该数组。

该生成器接收四个非负整数 $n$、$m$、$c$、$s$，其中 $n$ 和 $m$ 必须为正整数，$s$ 为非负整数，且 $c$ 需满足 $0 \leq c < m$。按如下规则构造长度为 $n$ 的数组 $a$：

• $a_1 = s \bmod m$，此处 $x \bmod y$ 表示 $x$ 除以 $y$ 所得的余数；
• 对所有满足 $1 < i \le n$ 的 $i$，有 $a_i = (a_{i-1} + c) \bmod m$。

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

此类数组的价格即为其生成器中参数 $m$ 的值。

亚历克斯有一个问题：对于他拥有的每个数组，他最多能获得多少钱？请帮助他判断：对每一个给定数组，是否存在四元组 $n$、$m$、$c$、$s$ 能够生成该数组；若存在，则求出最大的可能的 $m$ 值。

The first line contains a single integer $t$ ($1 \leq t \leq 10^5$) — the number of arrays.

The first line of array description contains a single integer $n$ ($1 \leq n \leq 10^5$) — the size of this array.

The second line of array description contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^9$ ) — elements of the array.

It is guaranteed that the sum of array sizes does not exceed $10^5$.

第一行包含一个整数 $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$。

For every array print:

• $-1$, if there are no such four numbers that generate this array;
• $0$, if $m$ can be arbitrary large;
• the maximum value $m$ and any appropriate $c$ ($0 \leq c \lt m$) in other cases.

对每个数组，输出：

• $-1$，如果不存在能生成该数组的四个数；
• $0$，如果 $m$ 可以任意大；
• 其他情况下，输出最大的 $m$ 值及任意一个合适的 $c$（满足 $0 \leq c \lt m$）。