Restoring the Expression
Contest: Codeforces Round 451 (Div. 2)
Difficulty rating: 2300
Tags: brute force, hashing, math

A correct expression of the form a+b=c was written; a, b and c are non-negative integers without leading zeros. In this expression, the plus and equally signs were lost. The task is to restore the expression. In other words, one character '+' and one character '=' should be inserted into given sequence of digits so that:

- character'+' is placed on the left of character '=',
- characters '+' and '=' split the sequence into three non-empty subsequences consisting of digits (let's call the left part a, the middle part — b and the right part — c),
- all the three parts a, b and c do not contain leading zeros,
- it is true that a+b=c.

It is guaranteed that in given tests answer always exists.

Input format:
The first line contains a non-empty string consisting of digits. The length of the string does not exceed 106.

Output format:
Output the restored expression. If there are several solutions, you can print any of them.

Note that the answer at first should contain two terms (divided with symbol '+'), and then the result of their addition, before which symbol'=' should be.

Do not separate numbers and operation signs with spaces. Strictly follow the output format given in the examples.

If you remove symbol '+' and symbol '=' from answer string you should get a string, same as string from the input data.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
12345168

Example output:
123+45=168

Example input:
099

Example output:
0+9=9

Editorial:
At first we should calculate "hash" by big prime module from the given string, and the base must be equal to 10 because we work with numbers. We can use prime module about 1015, if we will use multiple of long longs by module with help of long doubles.
After that we will brute the length of the result of summation, let this value is len3. Because when two numbers are added the result may have the same length as the larger term, or may have a length one greater than the length of the larger term it is enough to check the following cases (len1 — the length of the first term, len2 — the length of the second term):
• len1 = len3, len2 = n - len1 - len3
• len1 = len3 - 1, len2 = n - len1 - len3
• len2 = len3, len1 = n - len2 - len3
• len2 = len3 - 1, len1 = n - len2 - len3
For each case the check algorithm is the same. At first we should check that all parts have positive length, that the length len3 satisfies the conditions described at the beginning of the tutorial and that it part has no trailing spaces.
Now we should divide each part on 10 in the needed power, to bring the value of the calculated "hash" to the desired degree. To make it we can multiply each part on element, which is reverse to 10 by the used module, in the desired power. To find r which is reverse to 10 be the prime module MOD we should raising 10 to the power (MOD - 2) with help of binary power raising.
If after the described operations the sum of first to parts by used module equals to the value of third part, we found the answer and we should print corresponding parts.
You could also perform calculations on several smaller modules.