Grammy 有一个整数序列 $a_1, a_2, \dots, a_n$。她认为序列中的元素太大了，所以她决定给序列加上一个等差数列。形式化地，她可以选择两个非负整数 $s, d$，并对每个 $k \in [1, n]$，将 $s + kd$ 加到 $a_k$ 上。

由于我们想要破坏这个传说，请告诉她操作后元素模 $m$ 的和的最小值。注意，你应该最小化取模后的和。

输入格式

第一行包含两个整数 $n, m$ ($1 \le n \le 10^5, 1 \le m \le 10^9$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i < m$)，表示初始序列。

输出格式

输出恰好两行。

第一行包含一个整数，表示模 $m$ 后的最小元素和。

第二行包含两个整数 $s, d$ ($0 \le s, d < m$)，表示 Grammy 选择的整数。

如果存在多种解，输出任意一个即可。

样例

样例输入 1

6 24
1 1 4 5 1 4

样例输出 1

1
0 5

样例输入 2

7 29
1 9 1 9 8 1 0

样例输出 2

0
0 0