Ambiguous Result

The ACM (Advanced Cosmos Monitor) recorded a set of messages transmitted by alien race of Space Invaders. Unfortunately, the antenna used for recording only handles lower frequencies representing numbers and two arithmetical operators in space-invaderian language, while all parentheses (corresponding to a high frequency) were lost.

Since numbers are important for those 8-bit creatures, we really need to know what number ranges these messages belong to — please, write a program that can do this for us!


Input contains at most $1\ 500$ legal arithmetical expressions, each expression on a separate line. Each expression consists only of non-negative integers $x_ i$ ($0 \leq x_ i \leq 100$) and binary operators “+” and “*”. The expression starts with a number, then the operators and numbers alternate, and the last element is a number. Each expression contains $P$ numbers ($1 \leq P \leq 100$) and $P - 1$ operators. There are no parentheses, no other operators, no unary operator, etc.

The last input expression is followed by a line containing the single word “END”.


For each input line (not counting the final END), output one line containing the minimum and maximum values (separated by a single space) that are achievable by adding parentheses to the input in a way that forms a legal expression and computing the result of that expression.

For example, the minimum value for $2 + 1 \cdot 0$ input is achieved by $(2 + 1) \cdot 0$ and the maximum value is achieved by $2 + (1 \cdot 0)$. Therefore, you should print “0 2”.

It is guaranteed that for any placement of parentheses, the value of each parenthesis will be less than $2^{63}$. This means that also the maximal result will be between $0$ and $2^{63} - 1$, inclusive.

Sample Input 1 Sample Output 1
0 2
36 690
0 0
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
Source CTU Open 2011
License For educational use only

Please log in to submit a solution to this problem

Log in