← 返回题目列表

Codeforces · 763/C

C. Timofey 和重构

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

小蒂莫菲非常喜欢整数。不幸的是,他还很年轻,不能处理很大的整数,所以他对他最喜欢的素数 m 进行模运算。此外,蒂莫菲喜欢到处寻找算术级数。

他的生日礼物之一是一系列不同的整数 a1, a2, ..., an。 Timofey 想知道他是否可以重新排列序列的元素,从而使其成为以 m 为模的算术级数。

第一个元素 x 和差 d 的长度为 n 的算术级数模 m 是整数 x、x + d、x + 2d、...、x + (n - 1)·d 的序列,每个都以 m 为模。

输入

第一行包含两个整数 m 和 n (2 ≤ m ≤ 109 + 7, 1 ≤ n ≤ 105, m 是素数) — Timofey 最喜欢的素数模块和序列的长度。

第二行包含 n 个不同的整数 a1, a2, ..., an (0 ≤ ai < m) — 序列的元素。

输出

如果无法重新排列序列的元素,则打印 -1,使其成为以 m 为模的算术级数。

否则,打印两个整数 - 所获得的级数 x (0 ≤ x < m) 的第一个元素及其差 d (0 ≤ d < m)。

如果有多个答案,请打印其中任何一个。

示例

输入 #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