410712: GYM104090 A Modulo Ruins the Legend

Grammy has a sequence of integers $$$a_1,a_2,\ldots,a_n$$$. She thinks that the elements in the sequence are too large, so she decided to add an arithmetic progression to the sequence. Formally, she can choose two non-negative integers $$$s,d$$$, and add $$$s+kd$$$ to $$$a_k$$$ for each $$$k\in [1,n]$$$.

Since we want to ruin the legend, please tell her the minimum sum of elements modulo $$$m$$$ after the operation. Note that you should minimize the sum after taking the modulo.

The first line contains two integers $$$n,m$$$ ($$$1\leq n \leq 10^5$$$, $$$1 \leq m \leq 10^9$$$).

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \leq a_i < m$$$), denoting the initial sequence.

Output exactly two lines.

The first line contains one integer, denoting the minimum sum of elements modulo $$$m$$$.

The second line contains two integers $$$s,d$$$ ($$$0\le s,d<m$$$), denoting the integers chosen by Grammy. $$$\textbf{If there are multiple solutions, output any.}$$$

6 24
1 1 4 5 1 4

1
0 5

7 29
1 9 1 9 8 1 0

0
0 0