{"raw_statement":[{"iden":"statement","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_."},{"iden":"input","content":"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.\n\nThe second line contains _n_ **distinct** integers _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ < _m_) — the elements of the sequence."},{"iden":"output","content":"Print _\\-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."},{"iden":"examples","content":"Input\n\n17 5\n0 2 4 13 15\n\nOutput\n\n13 2\n\nInput\n\n17 5\n0 2 4 13 14\n\nOutput\n\n\\-1\n\nInput\n\n5 3\n1 2 3\n\nOutput\n\n3 4"}],"translated_statement":[{"iden":"statement","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如果有多个答案，输出任意一个即可。"},{"iden":"input","content":"第一行包含两个整数 #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]）——序列的元素。"},{"iden":"output","content":"如果无法重新排列序列使其成为模 #cf_span[m] 意义下的算术序列，请输出 _-1_。否则，输出两个整数——得到的序列的首项 #cf_span[x]（#cf_span[0 ≤ x < m]）和公差 #cf_span[d]（#cf_span[0 ≤ d < m]）。如果有多个答案，输出任意一个即可。"},{"iden":"examples","content":"输入1\n7 5\n0 2 4 13 15\n输出1\n13 2\n\n输入2\n7 5\n0 2 4 13 14\n输出2\n-1\n\n输入3\n5 3\n1 2 3\n输出3\n3 4"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ m $ be a prime, $ n \\in \\mathbb{N} $, and $ A = \\{a_1, a_2, \\dots, a_n\\} \\subset \\mathbb{Z}_m $ be a set of $ n $ distinct elements.\n\nWe seek to 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\\} $ equals $ A $ as a set.\n\n---\n\n**Formal Statement:**\n\nGiven:  \n- Prime modulus $ m \\geq 2 $,  \n- Integer $ 1 \\leq n \\leq 10^5 $,  \n- Set $ A \\subset \\mathbb{Z}_m $, $ |A| = n $, with $ A = \\{a_1, \\dots, a_n\\} $, all $ a_i $ distinct and $ 0 \\leq a_i < m $.\n\n**Question:**  \nDo there exist $ x, d \\in \\mathbb{Z}_m $ such that  \n$$\nA = \\left\\{ x + kd \\mod m \\;\\middle|\\; k = 0, 1, \\dots, n-1 \\right\\}?\n$$\n\nIf yes, output any such pair $ (x, d) $ with $ 0 \\leq x, d < m $.  \nIf no, output $-1$.\n\n---\n\n**Equivalent Condition:**  \nThe set $ A $ must be equal to an arithmetic progression modulo $ m $ of length $ n $, i.e., the elements of $ A $, when sorted in $ \\mathbb{Z}_m $, must form a sequence where consecutive differences (in the cyclic modular sense) are constant, up to rotation and reflection.\n\nNote: Since $ m $ is prime, $ \\mathbb{Z}_m $ is a field, and for $ d \\neq 0 $, the map $ k \\mapsto x + kd \\mod m $ is injective for $ k = 0, \\dots, n-1 $ as long as $ n \\leq m $, which holds.\n\nLet $ S $ be the sorted list of elements of $ A $ in $ [0, m-1] $:  \n$ s_0 < s_1 < \\dots < s_{n-1} $.\n\nLet $ \\Delta_i = s_{i+1} - s_i $ for $ i = 0, \\dots, n-2 $, and $ \\Delta_{n-1} = (s_0 + m) - s_{n-1} $ (the wrap-around gap).\n\nThen $ A $ is an arithmetic progression modulo $ m $ if and only if all the $ \\Delta_i $ are equal except possibly one, and that one (the wrap-around) equals $ n \\cdot d - \\sum_{i=0}^{n-2} \\Delta_i $, and the non-wrap differences are all equal to $ d $.\n\nBut a better approach:\n\nLet $ D $ be the multiset of differences $ (s_j - s_i) \\mod m $ for $ i < j $. In an AP of length $ n $, the set of pairwise differences must be exactly $ \\{ kd \\mod m \\mid 1 \\leq k \\leq n-1 \\} $, each appearing exactly $ n - k $ times.\n\nHowever, a simpler and more efficient characterization:\n\n> A set $ A \\subset \\mathbb{Z}_m $ of size $ n $ is an arithmetic progression modulo $ m $ if and only if the multiset of differences $ \\{ a_i - a_j \\mod m \\mid a_i > a_j \\} $ consists of multiples of a single generator $ d $, and the number of distinct differences is exactly $ n-1 $, each appearing with multiplicity proportional to their step.\n\nBut the most practical method:\n\n**Algorithmic Characterization (for formal output):**\n\nLet $ S = \\text{sorted}(A) $.\n\nLet $ g = \\gcd(\\Delta_0, \\Delta_1, \\dots, \\Delta_{n-2}, m) $, where $ \\Delta_i = s_{i+1} - s_i $.\n\nThen $ A $ is an AP modulo $ m $ if and only if:\n\n1. All non-wrap differences $ \\Delta_i $ for $ i = 0 $ to $ n-2 $ are equal to some $ d \\in \\mathbb{Z}_m $, **or**\n2. There is exactly one \"wrap-around\" gap, i.e., one $ \\Delta_i $ is large (greater than $ m/2 $), and all others are equal to some $ d $, and the wrap-around gap equals $ m - (n-1)d \\mod m $.\n\nActually, the cleanest way:\n\nLet $ d $ be the greatest common divisor of all pairwise differences $ (a_i - a_j) \\mod m $, $ i \\ne j $, in the additive group $ \\mathbb{Z}_m $. Since $ m $ is prime, the subgroup generated by the differences is cyclic.\n\nBut even simpler:\n\nLet $ S = \\text{sorted}(A) $. Define the set of consecutive differences $ D = \\{ s_{i+1} - s_i \\mid i = 0, \\dots, n-2 \\} \\cup \\{ s_0 + m - s_{n-1} \\} $.\n\nThen $ A $ is an AP modulo $ m $ if and only if:\n\n- All elements of $ D $ are equal to the same value $ d $, **except possibly one**, and that one equals $ m - (n-1)d \\mod m $.\n\nWait — that’s not right.\n\nActually, in a linear AP modulo $ m $, the elements are $ x, x+d, x+2d, \\dots, x+(n-1)d \\mod m $.\n\nWhen sorted in $ [0, m-1) $, the consecutive differences are either:\n\n- All equal to $ d $, if the progression does not wrap around, or\n- All equal to $ d $, except one difference which is $ d - m $ (i.e., a negative jump), which occurs when the progression wraps around.\n\nBut since we are sorting in $ [0, m) $, the wrap-around appears as a large gap: from $ s_{n-1} $ to $ s_0 + m $, so the wrap gap is $ s_0 + m - s_{n-1} $.\n\nIn a true AP modulo $ m $, the set of consecutive differences in the sorted list must consist of $ n-1 $ copies of $ d $, and one copy of $ m - (n-1)d $, but only if the progression wraps.\n\nActually, the sum of all consecutive differences in the circular sense must be $ m $:\n\n$$\n\\sum_{i=0}^{n-1} \\Delta_i = m\n$$\n\nwhere $ \\Delta_i $ are the $ n $ gaps between consecutive elements in the circular sorted order.\n\nIn an arithmetic progression modulo $ m $, the $ n $ gaps are: $ n-1 $ gaps of size $ d $, and one gap of size $ m - (n-1)d $.\n\nThus, the multiset of gaps must contain $ n-1 $ copies of some $ d $, and one copy of $ m - (n-1)d $.\n\nTherefore, the condition is:\n\nLet $ S = \\text{sorted}(A) $, and compute the $ n $ circular consecutive differences:\n\n$$\n\\Delta_i = \n\\begin{cases}\ns_{i+1} - s_i & \\text{if } i < n-1 \\\\\ns_0 + m - s_{n-1} & \\text{if } i = n-1\n\\end{cases}\n$$\n\nThen $ A $ is an AP modulo $ m $ if and only if:\n\n- Among the $ n $ values $ \\Delta_0, \\dots, \\Delta_{n-1} $, exactly $ n-1 $ are equal to some $ d \\in \\mathbb{Z}_m $, and the remaining one is $ m - (n-1)d \\mod m $.\n\nThen:\n\n- The common difference of the AP is $ d $.\n- The first term $ x $ is the smallest element in the sequence **before** the large gap, i.e., if the large gap is between $ s_{n-1} $ and $ s_0 $, then $ x = s_0 $; otherwise, if the large gap is between $ s_k $ and $ s_{k+1} $, then the progression \"wraps\" and the first term is $ s_{k+1} $, and the progression is $ s_{k+1}, s_{k+2}, \\dots, s_{n-1}, s_0, s_1, \\dots, s_k $, so $ x = s_{k+1} $.\n\nBut since we can output any valid $ (x, d) $, we can do:\n\n- If the large gap is between $ s_{n-1} $ and $ s_0 $, then $ x = s_0 $, $ d = \\text{common difference} $.\n- Else, if the large gap is between $ s_k $ and $ s_{k+1} $, then $ x = s_{k+1} $, $ d = \\text{common difference} $.\n\nBut note: $ d $ must satisfy $ (n-1)d \\equiv m - \\text{large gap} \\mod m $, and since the large gap is $ m - (n-1)d $, we have $ d = \\frac{m - \\text{large gap}}{n-1} \\mod m $, provided $ n > 1 $.\n\nIf $ n = 1 $, then any $ x = a_1 $, $ d = 0 $ works.\n\nSo the formal algorithmic condition is:\n\n---\n\n**Formal Mathematical Condition:**\n\nLet $ S = (s_0, s_1, \\dots, s_{n-1}) $ be the sorted sequence of $ A $ in increasing order.\n\nDefine the circular consecutive differences:\n\n$$\n\\Delta_i = \n\\begin{cases}\ns_{i+1} - s_i & \\text{for } 0 \\leq i \\leq n-2 \\\\\ns_0 + m - s_{n-1} & \\text{for } i = n-1\n\\end{cases}\n$$\n\nLet $ \\delta = \\min_{i \\ne j} \\Delta_i \\ne \\Delta_j $, i.e., let $ d $ be the value that appears $ n-1 $ times in $ \\Delta_0, \\dots, \\Delta_{n-1} $, and let $ \\Delta_{\\text{large}} $ be the other value.\n\nThen $ A $ is an arithmetic progression modulo $ m $ **if and only if**:\n\n- $ n = 1 $, or\n- $ n \\geq 2 $ and $ \\Delta_{\\text{large}} \\equiv m - (n-1)d \\pmod{m} $, and $ d \\ne 0 $, or\n- $ d = 0 $ and $ n = 1 $ (trivial), or if $ d = 0 $ and $ n > 1 $, then all $ a_i $ equal — but $ A $ has distinct elements, so $ d \\ne 0 $.\n\nSince elements are distinct, $ d \\ne 0 $.\n\nSo:\n\n> $ A $ is an AP mod $ m $ iff the multiset $ \\{ \\Delta_0, \\dots, \\Delta_{n-1} \\} $ contains exactly one value $ \\Delta_{\\text{large}} $ and $ n-1 $ copies of a single value $ d \\in \\mathbb{Z}_m \\setminus \\{0\\} $, and $ \\Delta_{\\text{large}} \\equiv m - (n-1)d \\pmod{m} $.\n\nThen, to recover $ x $:\n\nLet $ j $ be the index such that $ \\Delta_j = \\Delta_{\\text{large}} $.\n\nThen the progression starts at $ s_{(j+1) \\mod n} $, because the large gap follows $ s_j $, so the next element $ s_{(j+1) \\mod n} $ is the start of the progression.\n\nThus, $ x = s_{(j+1) \\mod n} $, and $ d $ is the common difference.\n\n---\n\n**Final Formal Output:**\n\nLet $ S = \\text{sorted}(A) $, $ n = |A| $.\n\nDefine $ \\Delta_i $ for $ i = 0, \\dots, n-1 $ as above.\n\nLet $ d $ be the value that occurs $ n-1 $ times in $ \\Delta $, and $ \\Delta_{\\text{large}} $ the other.\n\nIf $ n = 1 $:  \n  Output $ (s_0, 0) $\n\nElse if $ \\Delta_{\\text{large}} \\equiv m - (n-1)d \\pmod{m} $:  \n  Let $ j $ be the index with $ \\Delta_j = \\Delta_{\\text{large}} $  \n  Let $ x = s_{(j+1) \\mod n} $  \n  Output $ (x, d) $\n\nElse:  \n  Output $ -1 $\n\nNote: Since $ m $ is prime and $ d \\ne 0 $, $ d $ has an inverse mod $ m $, so $ d = \\frac{m - \\Delta_{\\text{large}}}{n-1} \\mod m $ is well-defined if the condition holds.\n\nBut we don’t need to compute $ d $ from $ \\Delta_{\\text{large}} $ — we get $ d $ from the majority value.\n\nSo the above condition is sufficient and necessary.\n\n---\n\n**Final Mathematical Formulation:**\n\nLet $ A \\subset \\mathbb{Z}_m $, $ |A| = n $, $ A $ distinct. Let $ S = (s_0 < s_1 < \\dots < s_{n-1}) $ be the sorted elements of $ A $.\n\nDefine $ \\Delta_i = \\begin{cases} s_{i+1} - s_i & \\text{if } i < n-1 \\\\ s_0 + m - s_{n-1} & \\text{if } i = n-1 \\end{cases} $\n\nLet $ \\mathcal{D} = \\{ \\Delta_0, \\dots, \\Delta_{n-1} \\} $.\n\nThen $ A $ is an arithmetic progression modulo $ m $ if and only if:\n\n- $ n = 1 $, or\n- $ n \\geq 2 $, and $ \\mathcal{D} $ contains exactly one distinct value $ \\Delta_{\\text{large}} $ appearing once, and another value $ d \\in \\mathbb{Z}_m \\setminus \\{0\\} $ appearing $ n-1 $ times, and $ \\Delta_{\\text{large}} \\equiv m - (n-1)d \\pmod{m} $.\n\nIf this holds, then let $ j \\in \\{0, \\dots, n-1\\} $ be the unique index such that $ \\Delta_j = \\Delta_{\\text{large}} $, and output $ x = s_{(j+1) \\mod n} $, $ d $.\n\nOtherwise, output $ -1 $.","simple_statement":null,"has_page_source":false}