{"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 arithmetical progressions everywhere.\n\nOne 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.\n\nArithmetical 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_.\n\n## Input\n\nThe 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.\n\nThe second line contains _n_ **distinct** integers _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ < _m_) — the elements of the sequence.\n\n## Output\n\nPrint _\\-1_ if it is not possible to rearrange the elements of the sequence so that is will be an arithmetical progression modulo _m_.\n\nOtherwise, print two integers — the first element of the obtained progression _x_ (0 ≤ _x_ < _m_) and its difference _d_ (0 ≤ _d_ < _m_).\n\nIf there are multiple answers, print any of them.\n\n[samples]","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_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] 取模。\n\n第一行包含两个整数 #cf_span[m] 和 #cf_span[n]（#cf_span[2 ≤ m ≤ 109 + 7]，#cf_span[1 ≤ n ≤ 105]，#cf_span[m] 是质数）——蒂莫菲最喜欢的质数模数和序列长度。\n\n第二行包含 #cf_span[n] 个 *互不相同* 的整数 #cf_span[a1, a2, ..., an]（#cf_span[0 ≤ ai < m]）——序列的元素。\n\n如果无法将序列重新排列成模 #cf_span[m] 的算术序列，请输出 _-1_。\n\n否则，输出两个整数——得到的序列的首项 #cf_span[x]（#cf_span[0 ≤ x < m]）和公差 #cf_span[d]（#cf_span[0 ≤ d < m]）。\n\n如果有多个答案，输出任意一个即可。\n\n## Input\n\n第一行包含两个整数 #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]）——序列的元素。\n\n## Output\n\n如果无法将序列重新排列成模 #cf_span[m] 的算术序列，请输出 _-1_。否则，输出两个整数——得到的序列的首项 #cf_span[x]（#cf_span[0 ≤ x < m]）和公差 #cf_span[d]（#cf_span[0 ≤ d < m]）。如果有多个答案，输出任意一个即可。\n\n[samples]","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 \\mathbb{Z}_m $ such that the multiset  \n$$\n\\{x + kd \\mod m \\mid k = 0, 1, \\dots, n-1\\}\n$$  \nis equal to $ A $ as a set.\n\n---\n\n**Formal Statement:**\n\nGiven:  \n- Prime $ m \\geq 2 $,  \n- Integer $ 1 \\leq n \\leq 10^5 $,  \n- Set $ A \\subset \\mathbb{Z}_m $, $ |A| = n $, $ A = \\{a_1, \\dots, a_n\\} $, all distinct.\n\nFind:  \n- $ x, d \\in \\mathbb{Z}_m $, $ 0 \\leq x, d < m $,  \n  such that  \n  $$\n  A = \\left\\{ x + kd \\mod m \\mid k = 0, 1, \\dots, n-1 \\right\\}.\n  $$\n\nIf no such $ x, d $ exist, output $-1$.  \nOtherwise, output any such pair $ (x, d) $.\n\n---\n\n**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).","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF764E","tags":[],"sample_group":[["17 5\n0 2 4 13 15","13 2"],["17 5\n0 2 4 13 14","\\-1"],["5 3\n1 2 3","3 4"]],"created_at":"2026-03-03 11:00:39"}}