Exact Carry Operations

You are given a non‐negative integer \(x\) (in decimal notation, without leading zeros) and a non‐negative integer \(k\). Your task is to find a non‐negative integer \(y\) (in decimal notation) such that when adding \(x\) and \(y\) using the standard column addition algorithm, exactly \(k\) carry operations occur. In addition, the length (number of digits) of \(y\) cannot exceed the length of \(x\). Note that \(y\) may contain leading zeros.

Column addition and carry: When adding two digits along with any incoming carry, if the sum is at least 10, then only the ones digit of the sum is written in that column and a carry of 1 is forwarded to the next (higher) column. Each such carry is counted as one carry operation. For instance, in the following figure the two red marked digits indicate two columns in which a carry was produced.

\(\textbf{Example:}\) If \(x = 95\) and you choose \(y = 10\), then the addition is done as follows:

  95
+ 10
----
 105

The addition of the tens digits yields \(9+1=10\) (with an incoming carry of 0), which causes a carry operation. The units addition \(5+0=5\) does not produce a carry. Hence exactly one carry occurs.

Your answer code should, given an input \(x\) and \(k\), produce one valid \(y\) that meets the requirements. If there is no solution, output -1 (although under the problem constraints a solution is guaranteed to exist for valid inputs).

Note on Implementation: Since the carry in column addition depends on the lower order digits, a common approach is to process the digits from right to left. Let the digits of \(x\) be \(x_0, x_1, \ldots, x_{n-1}\) where \(x_0\) is the least significant digit. For each position you can choose a digit for \(y\) (denoted by \(y_i\)) such that:

[ x_i + y_i + c_i \begin{cases} \ge 10 & \text{(carry produced, set }c_{i+1} = 1)\ < 10 & \text{(no carry, set }c_{i+1} = 0) \end{cases} ]

You need to decide the digits for \(y\) so that exactly \(k\) of the positions yield a carry. Moreover, the number \(y\) must have at most as many digits as \(x\) (if it has fewer digits, assume it has leading zeros).

inputFormat

The input consists of two space‐separated values on a single line: a non‐negative integer \(x\) (given as a string of digits with no leading zeros) and a non‐negative integer \(k\) (\(0 \le k \le |x|\)).

outputFormat

Output a non‐negative integer \(y\) (possibly with leading zeros) of length at most \(|x|\) such that adding \(x\) and \(y\) in the usual column addition way produces exactly \(k\) carry operations. If no such \(y\) exists, print -1.

sample

95 1

10