### COCI 2007/2008, Croatian Regional

## Task JEDNAKOST

While browsing a math book, Mirko found a strange equation of the form A=S. What makes the equation strange is that A and S are not the same. Mirko realized that the left side of the equation should have addition operations between some pairs of digits in A.

Write a program that inserts the **smallest number** of addition operations on the left side to make the
equation correct. The numbers in the corrected equation may contain arbitrary amounts of leading
zeros.

### Input

The first line contains the equation in the form A=S.

A and S will both be positive integers without leading zeros. They will be different.

A will contain **at most 1000 digits.**

S will be **less than or equal to 5000.**

**Note:** The input data will guarantee that a solution, although not necessarily unique, will always exist.

### Output

Output the corrected equation. If there are multiple solutions, output any of them.

### Examples

## Input143175=120 ## Output14+31+75=120 |
## Input5025=30 ## Output5+025=30 |
## Input999899=125 ## Output9+9+9+89+9=125 |

All Submissions

Best Solutions

**Point Value:** 17 (partial)

**Time Limit:** 1.00s

**Memory Limit:** 64M

**Added:** Aug 05, 2013

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...