Timofey and remoduling

题意翻译

给出 $m, n$（$m$ 为质数），以及一个长度为 $n$ 的数列 $\{a_n\}$。请你任意重排 $a_i$ 的顺序，使得 $a_i$ 是一个 $\bmod\ m$ 意义下的等差数列。 即，存在非负整数 $0 \leq x, d < m$ 使得对于 $1 \leq i \leq n$ 都满足 $a_i = (x + (i - 1)d) \bmod m$。 如果可行，输出任意一组 $x, d$ 的值；否则输出 $-1$。

题目描述

Little Timofey likes integers a lot. Unfortunately, he is very young and can't work with very big integers, so he does all the operations modulo his favorite prime $ m $ . Also, Timofey likes to look for arithmetical progressions everywhere. One of his birthday presents was a sequence of distinct integers $ a_{1},a_{2},...,a_{n} $ . Timofey wants to know whether he can rearrange the elements of the sequence so that is will be an arithmetical progression modulo $ m $ , or not. Arithmetical progression modulo $ m $ of length $ n $ with first element $ x $ and difference $ d $ is sequence of integers $ x,x+d,x+2d,...,x+(n-1)·d $ , each taken modulo $ m $ .

输入输出格式

输入格式

The first line contains two integers $ m $ and $ n $ ( $ 2<=m<=10^{9}+7 $ , $ 1<=n<=10^{5} $ , $ m $ is prime) — Timofey's favorite prime module and the length of the sequence. The second line contains $ n $ distinct integers $ a_{1},a_{2},...,a_{n} $ ( $ 0<=a_{i}&lt;m $ ) — the elements of the sequence.

输出格式

Print -1 if it is not possible to rearrange the elements of the sequence so that is will be an arithmetical progression modulo $ m $ . Otherwise, print two integers — the first element of the obtained progression $ x $ ( $ 0<=x&lt;m $ ) and its difference $ d $ ( $ 0<=d&lt;m $ ). If there are multiple answers, print any of them.

输入输出样例

输入样例 #1

17 5
0 2 4 13 15

输出样例 #1

13 2

输入样例 #2

17 5
0 2 4 13 14

输出样例 #2

-1

输入样例 #3

5 3
1 2 3

输出样例 #3

3 4