LISA - Pocket Money

Young people spend a lot of money on things like sweets, music CDs, mobile phones and so on. But most young girls/boys have one problem: Their pocket money is not enough for all these jolly things. Little Lisa Listig is one of these poor girls with a small pocket money budget. Last month her pocket money lasted only one week. So she decided to enter into negotiations with her father. Her father Tomm - a mathematician - had an incredibly ingenious idea: He wrote down some fancy digits with operators (+, *) in between them on a sheet of paper and allowed Lisa to insert brackets. Then he declared that the result of that arithmetic expression is Lisa's new pocket money. Now it's Lisa's task to maximize her pocket money. As her father was surprised what a huge sum of money Lisa got for her result, he decided to minimize the result of the expression for his son Manfred. Now it's your task to calculate the results obtained by Lisa and her father.

Input

The first line of input contains the number of testcases k (k< 5000). Each of the following k lines consists of an arithmetic expression. This expression consists of numbers (0-9) separated by one of the two operators '*' and '+'. There are no spaces between the characters. Each line contains less than 100 characters.

Output

For each expression output the result obtained by Lisa and the result obtained by her father separated by one space. The results of the calculations are smaller than 264.

Example

Input:
1
1+2*3+4*5

Output:
105 27

Two possible expressions for the first testcase:

105 = (1+2)*(3+4)*5
27  = 1+2*3+4*5

Added by:Simon
Date:2005-05-17
Time limit:32s
Source limit:8082B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL GOSU JS-RHINO
Resource:Ulm Algorithm Course SoSe 2005

hide comments
2014-10-10 02:49:13 Rajat (1307086)
!!!!!!!SPOILER ALERT!!!!!!!
Learnt a matrix multiplication application of DP and got AC in one go...
2014-06-14 17:54:52 Apoorv Gupta
What should be the answer for ->
2*0*3+7+1*0*3

It should be
42 0
2*((0*3+7+1*0)*3) = 42

However, solutions with answer 14 are getting ac, and the one with 42 are getting WA. Why so ?

2014-02-01 09:45:09 Amey Telawane
why time limit=32 seconds.? mine was done in 0.21 without using fast io..
2014-01-10 14:19:05 nitesh kumar
classical dp problem but presented differntly..
2013-12-29 08:05:23 Dewan Mahmud Raihan
Nice 2 state dp problem. :)
2013-12-25 12:18:33 Vladimir Torpski
This is a bit awful... I have a n^3 solution and got AC in 0.76 seconds?

Last edit: 2013-12-25 12:18:52
2013-12-07 22:08:20 Arpit Agarwal
Iterative > Recursive with memo
2013-10-24 00:43:05 nondescript
beautiful DP. thanks!
2013-10-18 22:42:43 Avaneesh Rastogi
The answer for 2+1*0*1+1 is >>
(2+(1*0))*(1+1)=4
It seems very easy to believe the answer to be 3 as follows >>
2+(1*0*1)+1=3

dont give up easily!


Last edit: 2013-10-25 20:49:55
2013-07-10 02:49:41 samuel
Nice DP!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.