Minimum Plus Insertion Sum

Given a string of the form A=B, where both \(A\) and \(B\) are positive integers without leading zeros, insert plus signs between some adjacent digits of \(A\) such that when the resulting expression is evaluated, it equals \(B\). You must use the least number of plus signs possible.

After inserting plus signs into \(A\), each segment (i.e. each summand) is allowed to have multiple leading zeros. For example, numbers like 00012 are permitted. The input is guaranteed to have at least one solution.

The final output should be in the format:

<modified A>=B

where <modified A> is the string \(A\) with plus signs inserted.

In mathematical terms, if we denote the digits of \(A\) by \(a_1a_2\ldots a_n\), you need to choose some positions between adjacent digits (if any) to insert a plus sign such that: \[ a_{1..i_1} + a_{(i_1+1)..i_2} + \cdots + a_{(i_k+1)..n} = B \] with the number of plus signs \(k\) minimized.

inputFormat

The input consists of a single line containing a string of the form A=B, where \(A\) and \(B\) are positive integers (without leading zeros).

outputFormat

Output a single line: the expression formed by inserting the minimum number of plus signs into \(A\) so that the arithmetic sum of the resulting numbers equals \(B\), followed immediately by an equals sign and then \(B\).

sample

123=6

1+2+3=6