Limits 1s, 512 MB

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 nn institutions and ithi^{th} institution has aia_i donors (where 1in1\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 kk. We hope that the total number of donors in the list will be a multiple of kk. 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(1n105)n(1\leq n\leq 10^5) and k(1k105)k(1\leq k\leq 10^5) representing the number of institutions and Muntasir’s lucky number respectively. The next line contains nn space-separated integers ai(0ai105)a_i (0\leq a_i\leq 10^5) representing number of donors from ithi^{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

InputOutput
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.


Submit

Login to submit.

Statistics

70% Solution Ratio
Saom.greenEarliest, May '21
steinumFastest, 0.0s
steinumLightest, 1.0 MB
AFattahShortest, 314B
Toph uses cookies. By continuing you agree to our Cookie Policy.