English · Original
Chinese · Translation
Formal · Original
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_ + 2_d_, ..., _x_ + (_n_ - 1)·_d_, each taken modulo _m_.
## Input
The first line contains two integers _m_ and _n_ (2 ≤ _m_ ≤ 109 + 7, 1 ≤ _n_ ≤ 105, _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_ < _m_) — the elements of the sequence.
## Output
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_ < _m_) and its difference _d_ (0 ≤ _d_ < _m_).
If there are multiple answers, print any of them.
[samples]
小蒂莫菲非常喜欢整数。不幸的是，他年纪太小，无法处理很大的整数，因此他所有的运算都在他最喜欢的质数 #cf_span[m] 下进行。此外，蒂莫菲喜欢到处寻找算术序列。
他生日收到的礼物是一个由 *互不相同* 整数组成的序列 #cf_span[a1, a2, ..., an]。蒂莫菲想知道，是否能将这个序列的元素重新排列，使得它成为一个模 #cf_span[m] 的算术序列。
模 #cf_span[m] 的长度为 #cf_span[n]、首项为 #cf_span[x]、公差为 #cf_span[d] 的算术序列，是指序列 #cf_span[x, x + d, x + 2d, ..., x + (n - 1)·d]，其中每一项都对 #cf_span[m] 取模。
第一行包含两个整数 #cf_span[m] 和 #cf_span[n]（#cf_span[2 ≤ m ≤ 109 + 7]，#cf_span[1 ≤ n ≤ 105]，#cf_span[m] 是质数）——蒂莫菲最喜欢的质数模数和序列长度。
第二行包含 #cf_span[n] 个 *互不相同* 的整数 #cf_span[a1, a2, ..., an]（#cf_span[0 ≤ ai < m]）——序列的元素。
如果无法将序列重新排列成模 #cf_span[m] 的算术序列，请输出 _-1_。
否则，输出两个整数——得到的序列的首项 #cf_span[x]（#cf_span[0 ≤ x < m]）和公差 #cf_span[d]（#cf_span[0 ≤ d < m]）。
如果有多个答案，输出任意一个即可。
## Input
第一行包含两个整数 #cf_span[m] 和 #cf_span[n]（#cf_span[2 ≤ m ≤ 109 + 7]，#cf_span[1 ≤ n ≤ 105]，#cf_span[m] 是质数）——蒂莫菲最喜欢的质数模数和序列长度。第二行包含 #cf_span[n] 个 *互不相同* 的整数 #cf_span[a1, a2, ..., an]（#cf_span[0 ≤ ai < m]）——序列的元素。
## Output
如果无法将序列重新排列成模 #cf_span[m] 的算术序列，请输出 _-1_。否则，输出两个整数——得到的序列的首项 #cf_span[x]（#cf_span[0 ≤ x < m]）和公差 #cf_span[d]（#cf_span[0 ≤ d < m]）。如果有多个答案，输出任意一个即可。
[samples]
Let $ m $ be a prime modulus, $ n \in \mathbb{N} $, and $ A = \{a_1, a_2, \dots, a_n\} \subset \mathbb{Z}_m $ a set of $ n $ distinct elements.
**Objective:** Determine whether there exist $ x, d \in \mathbb{Z}_m $ such that the multiset
$$
\{x + kd \mod m \mid k = 0, 1, \dots, n-1\}
$$
is equal to $ A $ as a set.
---
**Formal Statement:**
Given:
- Prime $ m \geq 2 $,
- Integer $ 1 \leq n \leq 10^5 $,
- Set $ A \subset \mathbb{Z}_m $, $ |A| = n $, $ A = \{a_1, \dots, a_n\} $, all distinct.
Find:
- $ x, d \in \mathbb{Z}_m $, $ 0 \leq x, d < m $,
such that
$$
A = \left\{ x + kd \mod m \mid k = 0, 1, \dots, n-1 \right\}.
$$
If no such $ x, d $ exist, output $-1$.
Otherwise, output any such pair $ (x, d) $.
---
**Note:** The progression is taken modulo $ m $, and the elements are interpreted as residues in $ \{0, 1, \dots, m-1\} $. The difference $ d $ may be zero only if $ n = 1 $. If $ n \geq 2 $, then $ d \neq 0 $ (since all elements are distinct).
API Response (JSON)
{
"problem": {
"name": "E. Timofey and remoduling",
"description": {
"content": "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",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF764E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "小蒂莫菲非常喜欢整数。不幸的是，他年纪太小，无法处理很大的整数，因此他所有的运算都在他最喜欢的质数 #cf_span[m] 下进行。此外，蒂莫菲喜欢到处寻找算术序列。\n\n他生日收到的礼物是一个由 *互不相同* 整数组成的序列 #cf_span[a1, a2, ..., an]。蒂莫菲想知道，是否能将这个序列的元素重新排列，使得它成为一个模 #cf_span[m] 的算术序列。\n\n模 #cf_spa...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Let $ m $ be a prime modulus, $ n \\in \\mathbb{N} $, and $ A = \\{a_1, a_2, \\dots, a_n\\} \\subset \\mathbb{Z}_m $ a set of $ n $ distinct elements.\n\n**Objective:** Determine whether there exist $ x, d \\in...",
"is_translate": false,
"language": "Formal"
}
]
}