У вас есть массив $$$A$$$ из $$$N$$$ целых неотрицательных чисел.
За одну операцию вы можете выбрать любой элемент массива $$$A_i$$$ и циклически сдвинуть его цифры на произвольное расстояние. При сдвиге допускается, что в начале полученной записи окажутся нули — они считаются частью записи, но не влияют на итоговое числовое значение.
Например, из числа $$$10032$$$ (цифры $$$1,0,0,3,2$$$) за одну операцию можно получить следующие записи при разных сдвигах: $$$10032$$$, $$$00321$$$, $$$03210$$$, $$$32100$$$, $$$21003$$$.
При подсчете суммы ведущие нули, очевидно, ни на что не влияют (то есть $$$00321$$$ равно $$$321$$$). Обратите внимание, что число $$$0$$$ не содержит ведущих нулей.
Всего разрешено применить операцию не более чем к $$$K$$$ элементам массива.
Требуется выбрать, какие элементы изменить (всего не более $$$K$$$ штук), чтобы сумма всех элементов полученного массива была минимально возможной.
В первой строке содержатся два целых числа $$$N$$$ и $$$K$$$ $$$(1 \le K \le N \le 2 \cdot 10^5)$$$ — размер массива и максимальное количество операций.
Во второй строке содержатся $$$N$$$ целых чисел $$$A_1, A_2, \ldots, A_N$$$ через пробел $$$(0 \le A_i \le 10^9)$$$ — элементы массива. Числа $$$A_i$$$ записаны без ведущих нулей.
В единственной строке выведите $$$N$$$ целых чисел $$$B_1, B_2, \ldots, B_N$$$ через пробел — массив, полученный после применения операций, с минимально возможной суммой $$$\sum\limits_{i=1}^{N} B_i$$$.
Каждое $$$B_i$$$ должно быть значением некоторого циклического сдвига числа $$$A_i$$$ ($$$B_i = A_i$$$ разрешено).
При этом количество индексов $$$i$$$, для которых $$$B_i$$$ получено сдвигом, отличным от нулевого (то есть $$$B_i$$$ не равно записи $$$A_i$$$ без сдвига), не должно превышать $$$K$$$.
Каждое $$$B_i$$$ выводится как обычное целое число без ведущих нулей: например, для $$$A_i = 10032$$$ сдвиг, дающий запись $$$00321$$$, выводится как $$$321$$$.
Если существует несколько массивов $$$B$$$ с минимально возможной суммой, разрешается вывести любой из них.
5 210032 203 7 100 980
321 203 7 100 98
3 21003 21 7
31 12 7
Пример 1.
Исходный массив: $$$10032, 203, 7, 100, 980$$$, допускается не более $$$K = 2$$$ операций.
В приведённом ответе сдвинуты два элемента: $$$10032$$$ и $$$980$$$.
Запись $$$10032$$$ (цифры $$$1,0,0,3,2$$$) сдвинута так, что первая цифра $$$1$$$ переносится в конец: получается запись $$$00321$$$, значение которой равно $$$321$$$.
Запись $$$980$$$ (цифры $$$9,8,0$$$) сдвинута так, что первые две цифры $$$9,8$$$ переносятся в конец: получается запись $$$098$$$, значение которой равно $$$98$$$.
Остальные элементы $$$203$$$, $$$7$$$, $$$100$$$ не сдвигаются и остаются равны $$$203$$$, $$$7$$$ и $$$100$$$ соответственно.
Итоговый массив: $$$321, 203, 7, 100, 98$$$, его сумма равна $$$321 + 203 + 7 + 100 + 98 = 729$$$.
Существуют и другие способы применения двух операций (например, к $$$203$$$ и $$$100$$$ или к $$$203$$$ и $$$10032$$$), но сумма $$$729$$$ — минимально возможная среди всех способов.
Пример 2.
Исходный массив: $$$1003, 21, 7$$$, допускается не более $$$K = 2$$$ операций.
В приведённом ответе сдвинуты элементы $$$1003$$$ и $$$21$$$.
Запись $$$1003$$$ (цифры $$$1,0,0,3$$$) сдвинута так, что первая цифра $$$1$$$ переносится в конец: получается запись $$$0031$$$, значение которой равно $$$31$$$.
Запись $$$21$$$ (цифры $$$2,1$$$) сдвинута так, что первая цифра $$$2$$$ переносится в конец: получается запись $$$12$$$, значение которой равно $$$12$$$.
Итоговый массив: $$$31, 12, 7$$$.
Обратите внимание: число $$$1003$$$ нельзя превратить в число $$$13$$$ из $$$31$$$, потому что фактически у вас остаётся $$$0031$$$, а не просто $$$31$$$.
