H. Spin the Wheel!
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$A$$$ of $$$N$$$ non-negative integers.

In one operation, you may choose any element $$$A_i$$$ of the array and cyclically shift its digits by an arbitrary amount. When shifting, leading zeros are allowed in the resulting representation — they are considered part of the representation, but do not affect the final numeric value.

For example, from the number $$$10032$$$ (digits $$$1,0,0,3,2$$$), in one operation you can obtain the following representations with different shifts: $$$10032$$$, $$$00321$$$, $$$03210$$$, $$$32100$$$, $$$21003$$$.

When computing the sum, leading zeros obviously do not matter (that is, $$$00321$$$ is equal to $$$321$$$). Note that the number $$$0$$$ does not contain leading zeros.

You are allowed to apply the operation to at most $$$K$$$ elements of the array.

You need to choose which elements to change (at most $$$K$$$ of them) so that the sum of all elements of the resulting array is as small as possible.

Input

The first line contains two integers $$$N$$$ and $$$K$$$ $$$(1 \le K \le N \le 2 \cdot 10^5)$$$ — the size of the array and the maximum number of operations.

The second line contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$ separated by spaces $$$(0 \le A_i \le 10^9)$$$ — the elements of the array. The numbers $$$A_i$$$ are written without leading zeros.

Output

Print $$$N$$$ integers $$$B_1, B_2, \ldots, B_N$$$ separated by spaces in a single line — the array obtained after applying the operations, with the minimum possible sum $$$\sum\limits_{i=1}^{N} B_i$$$.

Each $$$B_i$$$ must be the value of some cyclic shift of the number $$$A_i$$$ ($$$B_i = A_i$$$ is allowed).

At the same time, the number of indices $$$i$$$ for which $$$B_i$$$ is obtained by a non-zero shift (that is, $$$B_i$$$ is not equal to the representation of $$$A_i$$$ without shifting) must not exceed $$$K$$$.

Each $$$B_i$$$ is printed as an ordinary integer without leading zeros: for example, for $$$A_i = 10032$$$, a shift producing the representation $$$00321$$$ is printed as $$$321$$$.

If there are several arrays $$$B$$$ with the minimum possible sum, you may output any of them.

Examples
Input
5 2
10032 203 7 100 980
Output
321 203 7 100 98
Input
3 2
1003 21 7
Output
31 12 7
Note

Example 1.

Original array: $$$10032, 203, 7, 100, 980$$$, and at most $$$K = 2$$$ operations are allowed.

In the shown answer, two elements are shifted: $$$10032$$$ and $$$980$$$.

The representation of $$$10032$$$ (digits $$$1,0,0,3,2$$$) is shifted so that the first digit $$$1$$$ is moved to the end: the representation $$$00321$$$ is obtained, whose value is $$$321$$$.

The representation of $$$980$$$ (digits $$$9,8,0$$$) is shifted so that the first two digits $$$9,8$$$ are moved to the end: the representation $$$098$$$ is obtained, whose value is $$$98$$$.

The remaining elements $$$203$$$, $$$7$$$, $$$100$$$ are not shifted and remain equal to $$$203$$$, $$$7$$$, and $$$100$$$ respectively.

The resulting array is $$$321, 203, 7, 100, 98$$$, and its sum is $$$321 + 203 + 7 + 100 + 98 = 729$$$.

There are other ways to apply two operations (for example, to $$$203$$$ and $$$100$$$, or to $$$203$$$ and $$$10032$$$), but the sum $$$729$$$ is the minimum possible among all ways.

Example 2.

Original array: $$$1003, 21, 7$$$, and at most $$$K = 2$$$ operations are allowed.

In the shown answer, the elements $$$1003$$$ and $$$21$$$ are shifted.

The representation of $$$1003$$$ (digits $$$1,0,0,3$$$) is shifted so that the first digit $$$1$$$ is moved to the end: the representation $$$0031$$$ is obtained, whose value is $$$31$$$.

The representation of $$$21$$$ (digits $$$2,1$$$) is shifted so that the first digit $$$2$$$ is moved to the end: the representation $$$12$$$ is obtained, whose value is $$$12$$$.

The resulting array is $$$31, 12, 7$$$.

Note: the number $$$1003$$$ cannot be turned into $$$13$$$ from $$$31$$$, because in fact you get $$$0031$$$, not just $$$31$$$.