Description

假设你必须评估一种表达式，比如 A ×B × C × D × E ，其中 A 、 B 、 C 、 D 、 E 是矩阵。既然矩阵乘法满足结合率，那么乘法的顺序是任意的。矩阵连乘的乘法次数由相乘的顺序决定。例如， A 、 B 、 C 分别是50×10、10×20和20×5的矩阵。 现在有两种方案计算 A × B × C ，即( A × B )× C 和 A×( B × C )。第1种要进行15 000次乘法运算，而第2种只进行3 500次乘法运算。写程序，计算给定矩阵表达式需要进行多少次乘法运算。

Format

Input

输入包含矩阵和表达式两部分。

在第1部分，第1行包含一个整数$n$ $（1≤n ≤26）$，代表矩阵的个数；接下来的$n$ 行，每行都包含了一个大写字母来表示矩阵的名称，以及两个整数来表示矩阵的行数和列数。

第2部分是一个矩阵或矩阵表达式，严格遵守以下的语法：

SecondPart = Line { Line }

Line = Expression

Expression = Matrix | "(" Expression Expression ")"

Matrix = "A" | "B" | "C" | ... | "X" | "Y" | "Z"

Output

对于每一个表达式，如果乘法无法进行，则输出“$error$”，否则输出所需的乘法运算次数。

Samples

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))

0
0
0
error
10000
error
3500
15000
40500
47500
15125

来源

UVA442