You are given an array consisting of $n$ integers $a_1, a_2, \dots, a_n$, and a positive integer $m$. It is guaranteed that $m$ is a divisor of $n$.
In a single move, you can choose any position $i$ between $1$ and $n$ and increase $a_i$ by $1$.
Let's calculate $c_r$ ($0 \le r \le m-1)$ — the number of elements having remainder $r$ when divided by $m$. In other words, for each remainder, let's find the number of corresponding elements in $a$ with that remainder.
Your task is to change the array in such a way that $c_0 = c_1 = \dots = c_{m-1} = \frac{n}{m}$.
Find the minimum number of moves to satisfy the above requirement.
## Input
The first line of input contains two integers $n$ and $m$ ($1 \le n \le 2 \cdot 10^5, 1 \le m \le n$). It is guaranteed that $m$ is a divisor of $n$.
The second line of input contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$), the elements of the array.
## Output
In the first line, print a single integer — the minimum number of moves required to satisfy the following condition: for each remainder from $0$ to $m - 1$, the number of elements of the array having this remainder equals $\frac{n}{m}$.
In the second line, print **any** array satisfying the condition and can be obtained from the given array **with the minimum number of moves**. The values of the elements of the resulting array must not exceed $10^{18}$.
[samples]
你被给定一个由 $n$ 个整数 $a_1, a_2, dots.h, a_n$ 组成的数组，以及一个正整数 $m$。保证 $m$ 是 $n$ 的因数。
在一次操作中，你可以选择任意位置 $i$（$1 \leq i \leq n$）并将 $a_i$ 增加 $1$。
令 $c_r$（$0 \leq r \leq m - 1$）表示数组中除以 $m$ 后余数为 $r$ 的元素个数。换句话说，对于每个余数，统计数组中具有该余数的元素数量。
你的任务是通过修改数组，使得 $c_0 = c_1 = dots.h = c_{m - 1} = \frac{n}{m}$。
求满足上述要求所需的最少操作次数。
输入的第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 2 \cdot 10^5$, $1 \leq m \leq n$）。保证 $m$ 是 $n$ 的因数。
第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$（$0 \leq a_i \leq 10^9$），表示数组的元素。
第一行输出一个整数——满足以下条件所需的最少操作次数：对于每个从 $0$ 到 $m - 1$ 的余数，数组中具有该余数的元素个数等于 $\frac{n}{m}$。
第二行输出任意一个满足条件且可通过最少操作次数从原数组得到的数组。结果数组的元素值不得超过 $10^{18}$。
## Input
输入的第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 2 \cdot 10^5$, $1 \leq m \leq n$）。保证 $m$ 是 $n$ 的因数。第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$（$0 \leq a_i \leq 10^9$），表示数组的元素。
## Output
第一行输出一个整数——满足以下条件所需的最少操作次数：对于每个从 $0$ 到 $m - 1$ 的余数，数组中具有该余数的元素个数等于 $\frac{n}{m}$。第二行输出任意一个满足条件且可通过最少操作次数从原数组得到的数组。结果数组的元素值不得超过 $10^{18}$。
[samples]
**Definitions:**
- Let $ n, m \in \mathbb{Z}^+ $, with $ m \mid n $.
- Let $ \mathbf{a} = (a_1, a_2, \dots, a_n) \in \mathbb{Z}_{\geq 0}^n $ be the input array.
- Let $ c_r = \left| \{ i \in [n] : a_i \equiv r \pmod{m} \} \right| $ for $ r \in \{0, 1, \dots, m-1\} $.
- Target: $ c_r = \frac{n}{m} $ for all $ r \in \{0, 1, \dots, m-1\} $.
**Constraints:**
- Only allowed operation: increment any $ a_i $ by 1 (any number of times).
- All increments are non-negative and preserve $ a_i \in \mathbb{Z}_{\geq 0} $.
- Final values must satisfy $ \forall i, a_i' \geq a_i $, and $ a_i' \leq 10^{18} $.
**Objective:**
Minimize total number of moves:
$$
\min \sum_{i=1}^n (a_i' - a_i)
$$
subject to:
$$
\left| \left\{ i : a_i' \equiv r \pmod{m} \right\} \right| = \frac{n}{m}, \quad \forall r \in \{0, 1, \dots, m-1\}.
$$
**Strategy (Formalized):**
1. For each element $ a_i $, define its residue $ r_i = a_i \bmod m $.
2. Let $ \text{count}[r] = \left| \{ i : r_i = r \} \right| $ for $ r \in [0, m-1] $.
3. For each residue $ r $, if $ \text{count}[r] > \frac{n}{m} $, we must convert $ \text{count}[r] - \frac{n}{m} $ elements with residue $ r $ to some other residue $ s $ where $ \text{count}[s] < \frac{n}{m} $.
4. To minimize total increments, for each "excess" element with residue $ r $, assign it to the *next* deficit residue $ s > r $ (cyclically), using minimal increments: $ (s - r) \bmod m $.
5. Use a greedy cyclic assignment: process residues in order $ 0 \to 1 \to \dots \to m-1 \to 0 $, carry over excess to next deficit residue.
**Formal Output Requirements:**
- Let $ \mathbf{a}' = (a_1', a_2', \dots, a_n') $ be the resulting array.
- Each $ a_i' = a_i + d_i $, where $ d_i \geq 0 $, and $ d_i \equiv (s - r_i) \pmod{m} $ for target residue $ s $, minimized.
- Total moves: $ \sum_{i=1}^n d_i $.
**Algorithmic Core (Mathematical Formulation):**
Let $ k = \frac{n}{m} $.
Let $ \text{excess}[r] = \max\left(0, \text{count}[r] - k\right) $,
$ \text{deficit}[r] = \max\left(0, k - \text{count}[r]\right) $.
We construct a list of source indices (elements with excess residue) and target residues (deficit residues), ordered cyclically.
For each residue $ r = 0 $ to $ m-1 $:
- While $ \text{excess}[r] > 0 $:
- Find the smallest $ s \in \{r, r+1, \dots, m-1, 0, \dots, r-1\} $ such that $ \text{deficit}[s] > 0 $.
- Assign one excess element from residue $ r $ to target residue $ s $, requiring $ (s - r) \bmod m $ increments.
- Decrement $ \text{excess}[r] $ and $ \text{deficit}[s] $ by 1.
- Add $ (s - r) \bmod m $ to total moves.
To reconstruct $ \mathbf{a}' $:
For each element $ a_i $ with residue $ r_i $, assign it to target residue $ s $ as above, and set $ a_i' = a_i + ((s - r_i) \bmod m) $.
**Final Mathematical Statement:**
> Minimize $ \sum_{i=1}^n (a_i' - a_i) $,
> subject to $ \left| \{ i : a_i' \equiv r \pmod{m} \} \right| = \frac{n}{m} $ for all $ r \in \{0,1,\dots,m-1\} $,
> and $ a_i' \geq a_i $, $ a_i' \in \mathbb{Z} $,
> where each increment $ a_i' - a_i $ is the minimal non-negative integer such that $ a_i' \equiv s \pmod{m} $ for a target residue $ s $ assigned via greedy cyclic matching of excess to deficit residues.