Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3510
Boring Assignment Expressions

Time Limit: 2 Seconds      Memory Limit: 65536 KB      Special Judge

There are multiple assignment expressions. Each of them is defined by the following BNFs.

  • assignment-expression ::= variable "=" expressioin
  • expression ::= positive-digit | variable | "(" expression "*" expression ")" | "(" expression "+" expressioin ")"
  • positive-digit ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

Each variable is a string of uppercase letters. The rule to calculate an assignment expression is the same as in the C programming language. An assignment cannot be calculated unless all variables on the right have assigned value from previous calculation. Variable can be assigned more than once.

Now, you need to select some assignment expressions and put them in order to make sure all variables have assigned values and the sum of the final values of all variables is minimal.

Input

Multiple test cases. For each case, the first line is the number of assignment expressions and then one expression per line.

No more than 10000 assignment expressions. No more than 2000 variables in each case. Length of variable is no more than 7. Length of each assignment expression is no more than 1000. There will always be a space beween tokens in expression. There will always be an empty line between test cases.

Output

For each test case. Output the minimal sum of final values of all variables in the first line. Then output your selected expressions one expression per line in exact form as in the input.

If there is no possible answer or the minimal sum cannot be expressed in a unsigned 64-bit integer. Output "stupid expressions!" instead.

Sample Input

2
A = ( B * 2 )
B = ( A + 1 )

7
A = 1
B = 3
C = ( ( A + B ) * A )
C = ( 2 * ( A * B ) )
C = ( ( A + ( 2 * B ) ) + A )
A = ( ( C + B ) + A )
B = ( A + 1 )

Sample Output

stupid expressions!
6
A = 1
B = ( A + 1 )
C = ( ( A + B ) * A )

Author: CUI, Tianyi
Contest: ZOJ Monthly, July 2011
Submit    Status