D. Уравняй остатки
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан массив, состоящий из $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$, и натуральное число $$$m$$$. Гарантируется, что $$$m$$$ делит $$$n$$$ без остатка.

За один ход можно выбрать произвольный индекс $$$i$$$ от $$$1$$$ до $$$n$$$ и увеличить элемент $$$a_i$$$ на $$$1$$$.

Пусть $$$c_r$$$ ($$$0 \le r \le m-1)$$$ — количество элементов, которые имеют остаток $$$r$$$ при делении на $$$m$$$. Иными словами, подсчитаем количество элементов массива $$$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}$$$.

Примеры
Входные данные
6 3
3 2 0 6 10 12
Выходные данные
3
3 2 0 7 10 14
Входные данные
4 2
0 1 2 3
Выходные данные
0
0 1 2 3