← 返回题目列表

Codeforces · 999/D

D. 均衡余数

中文机器翻译题面 查看原题

给定一个由 $$$n$$$ 整数 $$$a_1、a_2、\dots、a_n$$$ 和一个正整数 $$$m$$$ 组成的数组。保证 $$$m$$$ 是 $$$n$$$ 的约数。

在一次移动中,您可以选择 $$$1$$$ 和 $$$n$$$ 之间的任意位置 $$$i$$$ 并将 $$$a_i$$$ 增加 $$$1$$$。

让我们计算 $$$c_r$$$ ($$$0 \le r \le m-1)$$$ — 除以 $$$m$$$ 后具有余数 $$$r$$$ 的元素数量。换句话说,对于每个余数,让我们找到 $$$a$$$ 中与该余数对应的元素的数量。

您的任务是以 $$$c_0 = c_1 = \dots = c_{m-1} = \frac{n}{m}$$$ 的方式更改数组。

求满足上述要求的最小移动次数。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5, 1 \le m \le n$$$)。保证 $$$m$$$ 是 $$$n$$$ 的约数。

输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$),即数组的元素。

输出

在第一行中,打印一个整数 - 满足以下条件所需的最小移动次数:对于从 $$$0$$$ 到 $$$m - 1$$$ 的每个余数,具有该余数的数组元素的数量等于 $$$\frac{n}{m}$$$。

在第二行中,打印满足条件并且可以从给定数组中以最少移动次数获得的任何数组。结果数组的元素值不得超过 $$$10^{18}$$$。

示例

输入 #1

6 3
3 2 0 6 10 12

输出 #1

3
3 2 0 7 10 14

输入 #2

4 2
0 1 2 3

输出 #2

0
0 1 2 3