Matrix Chain Multiplication

Time limit1sMemory limit128 MB

Summary

Given matrices with dimensions and fully parenthesized products, report the elementary multiplication count or an error if dimensions mismatch.

Level: Medium4 of 10
Topics: Stack, Recursion, Implementation
Solved: No attempts yet

Problem

Suppose you have to evaluate an expression like $A\*B\*C\*D\*E$ , where A, B, C, D and E are matrices.

Since matrix multiplication is associative, the order in which the multiplications are performed is arbitrary. However, the number of elementary multiplications needed depends strongly on the evaluation order you choose.

For example, let $A$ be a $50 \times 10$ matrix, $B$ a $10 \times 20$ matrix, and $C$ a $20 \times 5$ matrix.

There are two different strategies to compute $A\*B\*C$ , namely $(A\*B)\*C$ and $A\*(B\*C)$ .

The first one takes 15000 elementary multiplications, but the second one only 3500.

Your job is to write a program that determines the number of elementary multiplications needed for a given evaluation strategy.

Input

The input consists of two parts: a list of matrices and a list of expressions.

The first line contains one integer $n$ ( $1 \le n \le 26$ ), the number of matrices. Each of the next $n$ lines contains one capital letter (the name of a matrix) and two integers (its number of rows and columns).

The second part strictly adheres to the following syntax, given in EBNF.

SecondPart = Line { Line } <EOF>
Line       = Expression <CR>
Expression = Matrix | "(" Expression Expression ")"
Matrix     = "A" | "B" | "C" | ... | "X" | "Y" | "Z"

Each line holds one expression, and expressions continue until the end of the file.

Output

For each expression in the second part of the input, print one line containing the word "error" if evaluation of the expression leads to an error due to non-matching matrices. Otherwise print one line containing the number of elementary multiplications needed to evaluate the expression in the way specified by the parentheses.

Examples3

Example 1

Input

9
A 50 10
B 10 20
C 20 5
D 30 35
E 35 15
F 15 5
G 5 10
H 10 20
I 20 25
A
B
C
(AA)
(AB)
(AC)
(A(BC))
((AB)C)
(((((DE)F)G)H)I)
(D(E(F(G(HI)))))
((D(EF))((GH)I))

Expected output

Example 2
Input
```
1
A 2 3
A
```
Expected output
```
0
```
Example 3
Input
```
2
A 2 3
B 3 4
(AB)
```
Expected output
```
24
```