Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Sum & Multiple

By freedom_seeker · 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.


    Discussion

    Statistics


    69% Solution Ratio

    Saom.greenEarliest, 1w ago

    steinumFastest, 0.0s

    steinumLightest, 1.0 MB

    Fahim35Shortest, 525B

    Submit

    Login to submit

    Related Contests