Hacking the Screen

Parse an arithmetic formula with square roots and fractions drawn as ASCII art up to three lines high and print its integer value.

Medium7ImplementationRecursionMathNo attempts yetTime limit1sMemory limit256 MB

Problem

The zoo management spent a long time looking for a way to bring more children to the zoo. The answer turned out to be a big screen just past the entrance that shows short quizzes. The child in the crowd who shouts out the answer first gets one day of free entry. The screen became popular fast, and several kinds of quizzes now run on it. One kind is a math quiz with arithmetic on integers.

The management worries that older siblings and friends of the children will work out a way to beat the screen: photograph it with a phone, run image recognition software that pulls the formula out of the picture, evaluate the formula, and pass the answer to the phone holder, who shouts it out at once.

Your task is to judge how hard such software is to write. Start with a toy version of the problem: read a formula that has already been preprocessed into ASCII art, and evaluate it.

Input

The input holds several test cases. The first line of each test case has two integers RR and CC (1R31 \le R \le 3, 1C10001 \le C \le 1000). Each of the next RR lines holds CC characters. The whole matrix of R×CR \times C characters is one arithmetic formula written in ASCII art and generated by this set of rules:

 FORMULA -> COMPLEX | FORMULA + COMPLEX | FORMULA - COMPLEX

 COMPLEX -> SQRT | FRACTION | TERM
             ______
    SQRT -> \/SIMPLE

            SIMPLE
FRACTION -> ======
            SIMPLE

  SIMPLE -> TERM | SIMPLE + TERM | SIMPLE - TERM

    TERM -> INTEGER | INTEGER * TERM

 INTEGER -> 0 | 1 | 2 | 3 | ... | 999999 | 1000000

A few more rules fix the layout of the formula.

  • The horizontal bar of each SQRT is made of one or more underscores (_, ASCII code 95) and it always sits on the uppermost line of the formula on the screen.
  • When the formula takes exactly two lines, the first line holds only the horizontal bars of the SQRT parts of the formula.
  • When the formula takes exactly three lines, every TERM and every arithmetic symbol that belongs to no FRACTION and no SQRT sits on the second line of the formula on the screen.
  • The horizontal bar of a SQRT is exactly as long as the SIMPLE under the bar.
  • The fraction bar of a FRACTION is made of one or more equality signs, and its length is the larger of the length of the SIMPLE above the bar and the length of the SIMPLE below it. Spaces pad the shorter of the two to the width of the bar.
  • Exactly one space comes before and after each arithmetic symbol (+, -, *) on a given line.
  • The formula fits the R×CR \times C matrix exactly. No blank column stands in front of the whole formula or behind it.

The formula is evaluated by the standard rules of arithmetic. Each FORMULA and each TERM is evaluated from left to right. Each SIMPLE is evaluated from left to right as well, with the standard rule that multiplication binds tighter than addition and subtraction. SQRT and FRACTION are evaluated the standard way. The value of every evaluated FORMULA, COMPLEX, SQRT, FRACTION, SIMPLE and TERM is an integer whose absolute value is at most 1000000, so the number under a root is always a perfect square and a fraction always divides exactly.

One empty line follows each test case. The input ends with a line holding two zeros.

Output

For each test case print a separate line with the value VV of the input formula.