A=S

Time limit1sMemory limit128 MB

Summary

Insert plus signs between digits of a huge number A so the resulting sum equals a small target S, using as few plus signs as possible.

Level: Medium7 of 10
Topics: Dynamic programming, String, Math
Solved: No attempts yet

Problem

An equation A=S is given. The value of A on the left may be different from the value of S on the right.

Insert + signs between digits of A, if needed, so that the sum of the terms on the left becomes S. You may not reorder digits, and every digit must be used exactly once. A term created after insertion may have leading zeroes, and it is interpreted as an integer.

At least one valid expression is always guaranteed to exist.

Input

The first line contains an equation A=S. A and S are positive integers that do not start with 0. The length of A is at most 1,000 digits, and S is at most 5,000.

Output

Print one expression made by inserting + signs into A so that the equation is true.

If there are multiple valid expressions, print one with the minimum number of + signs. If there are still multiple such expressions, print any one of them.

Examples3

Example 1
Input
```
143175=120
```
Expected output
```
14+31+75=120
```
Example 2
Input
```
5025=30
```
Expected output
```
5+025=30
```
Example 3
Input
```
999899=125
```
Expected output
```
9+9+9+89+9=125
```