This page is still under construction.

Parts of this page are still being built. What you see may change.

What a Horrible and Dreadful Formula

Time limit1sMemory limit256 MB

Summary
Given a string where digits were replaced by English number words, recover the original arithmetic expression or report that none exists, then evaluate it left to right.
Level

Hard8 of 10

Topics
String, Implementation, Brute force, Simulation
Solved
No attempts yet

Problem

A person who stared at numbers all day long lost his mind and did something dreadful. Thinking that if he did not want to see numbers, he could simply erase them, he wrote the following dreadful string.

ONETWOTHREEFOUR+TWOTHREEFOURFIVE=

That is right. As long as numbers are not visible, it is fine. So, looking at the table below, he replaced every digit with an English word.

DigitEnglish word
0ZERO
1ONE
2TWO
3THREE
4FOUR
5FIVE
6SIX
7SEVEN
8EIGHT
9NINE

But alas, while looking at the string, the person who wrote it lost consciousness. Let us look at the string, compute the original expression, and tell him the answer. If the expression before conversion can be determined exactly and the answer can be computed, output that answer. If no expression before conversion is possible, output "Madness!".

The expression before conversion starts with a positive integer, then positive integers and operators alternate, the last operator is =, and = appears only at the end of the expression. The operators that appear are +, -, x, /, and =, five in total. Unlike the usual order of operations, calculation proceeds from left to right, and when the / operation produces a non-integer, it is rounded toward zero. For example, 1.8 rounds to 1, and -1.8 rounds to -1.

Input

A string consisting of uppercase English letters and +,-,x,/,= is given. The string ends with =, and does not start with an operator. = always appears only at the end of the string. "ZERO" never appears at the start of the string or immediately after an operator.

The given string SS has length 4≤∣S∣≤100,0004 ≤ \lvert S\rvert ≤ 100,000, and every number contained in the string is between 11 and 1,000,0001,000,000 inclusive.

Output

If no expression before conversion is possible, output Madness!

If a possible expression exists, output that expression on the first line, and on the second line output the value of the expression with every digit converted back to an English word.

Constraints

The absolute value of every number appearing in the answer and in the calculation process is less than 101510^{15}.

Examples5

  1. Example 1

    Input
    ONETWOTHREEFOUR+FIVESIXSEVEN=
    
    Expected output
    1234+567=
    ONEEIGHTZEROONE
    
  2. Example 2

    Input
    FIVEZEROxTWOTWO-ONEONEONEONE=
    
    Expected output
    50x22-1111=
    -ONEONE
    
  3. Example 3

    Input
    ONE-SIX/THREE=
    
    Expected output
    1-6/3=
    -ONE
    
  4. Example 4

    Input
    ONE+-THREE=
    
    Expected output
    Madness!
    
  5. Example 5

    Input
    ONETWOFIVENINEEIGHTSEVEN=
    
    Expected output
    125987=
    ONETWOFIVENINEEIGHTSEVEN