RAPL community is raising money for the treatment of Muntasir’s mother. So we have a list to do this charitable work. But we find it difficult. Help us to do it perfectly.

You are given the list of the number of donors from different institutions. There are $n$ institutions and $i^{th}$ institution has $a_i$ donors (where $1\leq i\leq n$). Institutions are ordered alphabetically in the list. We hope that every institution has at least one more donor than its previous institution on the list.

Muntasir has a lucky number $k$. We hope that the total number of donors in the list will be a multiple of $k$. You can increase the number of donors of any institution. So your task is to find the minimum number of additional donors we need to match the criteria and print the final list.

Input

The first line contains two integers $n(1\leq n\leq 10^5)$ and $k(1\leq k\leq 10^5)$ representing the number of institutions and Muntasir’s lucky number respectively. The next line contains $n$ space-separated integers $a_i (0\leq a_i\leq 10^5)$ representing number of donors from $i^{th}$ institution.

Output

In the first line, print a single integer representing the number of minimum additional donors we need. In the next line, you should print the final list that matches the given criteria. If there are multiple such lists, print any of them.

Sample

Input

Output

5 40
2 4 1 3 9

21
4 6 8 10 12

NOTE: Here, our aim is to make the sum of all elements a multiple of 40. The sum of our output array (4+6+8+10+12=40) is a multiple of 40. Moreover we have at least one more donor from every institution than the previous one.