Restore an Addition Equation

Time limit2sMemory limit128 MB

Summary

Fill the ? digits in an addition equation A+B=C with digits (no leading zeros) so the sum holds, maximizing C then A.

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

Problem

An addition equation has the form A+B=C. The values A, B, and C are nonnegative integers. A number may not start with 0, unless the number has exactly one digit. Some digits in the equation are written as ?.

Restore the equation by replacing every ? with a digit so that the equation is true. If several restorations are possible, output one with the largest value of C. If there is still more than one, output one with the largest value of A.

Input

The first line contains the equation. Its length is at most 50 characters.

Output

Print the restored equation. If it is impossible, print -1.

Examples5

Example 1
Input
```
5+?=?4
```
Expected output
```
5+9=14
```
Example 2
Input
```
?+?=4
```
Expected output
```
4+0=4
```
Example 3
Input
```
?2+?2=4
```
Expected output
```
-1
```
Example 4
Input
```
??+1=1?
```
Expected output
```
18+1=19
```
Example 5
Input
```
???+?=???0
```
Expected output
```
999+1=1000
```