Molecular Formula

Time limit3sMemory limit128 MB

Summary

Parse a nested molecular formula with repetition counts and atomic weight lookups to compute total molecular weight, or report UNKNOWN.

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

Problem

Write a program that computes the weight of a molecule described by a molecular formula in a virtual chemistry. As in real chemistry, each molecular formula represents a molecule made of one or more atoms, though it need not be chemically realistic.

An atom is written as an atomic symbol: either a single capital letter, or a capital letter followed by a small letter. For example, H and He are atomic symbols.
A molecular formula is a non-empty sequence of atomic symbols. For example, HHHeHHHe represents a molecule made of four H atoms and two He atoms.
A repetition of the same sub-formula, $X$ written $n$ times in a row (with $n$ an integer from $2$ to $99$ inclusive), can be abbreviated to (X)n. The parentheses may be omitted when $X$ is a single atomic symbol. For example, HHHeHHHe may also be written as H2HeH2He, (HHHe)2, (H2He)2, or ((H)2He)2.

The set of all molecular formulae can be viewed as a formal language. Summarizing the description above, the syntax of molecular formulae is defined as follows.

     Molecule → Atom | Atom Number | ( Molecule ) Number | Molecule Molecule
         Atom → CapitalLetter | CapitalLetter SmallLetter
       Number → 2 | 3 | 4 | · · · | 97 | 98 | 99
CapitalLetter → A | B | C | · · · | X | Y | Z
  SmallLetter → a | b | c | · · · | x | y | z

Each atom has its own atomic weight. The molecular weight is the sum of the weights of the constituent atoms. For example, if the atomic weights of H and He are $1$ and $4$ , then the molecule written (H2He)2 weighs $12$ .

Input

The input has two parts.

The first part is the Atomic Table: several lines, each containing an atomic symbol, one or more spaces, and its atomic weight (a positive integer at most $1000$ ). No two lines share the same atomic symbol. This part ends with a line containing only END_OF_FIRST_PART.

The second part is a sequence of lines, each a molecular formula of at most $80$ characters and containing no spaces. A molecule contains at most $105$ atoms. Some atomic symbols in a formula may be absent from the Atomic Table. This sequence is terminated by a line containing a single 0.

Output

For each formula in the second part, print one line. If every atomic symbol of the formula appears in the Atomic Table, print its molecular weight as an integer; otherwise print UNKNOWN. Print no extra characters.

Examples7

Example 1

Input

H 1
He 4
C 12
O 16
F 19
Ne 20
Cu 64
Cc 333
END_OF_FIRST_PART
H2C
(MgF)2As
Cu(OH)2
H((CO)2F)99
0

Expected output

14
UNKNOWN
98
7426

Example 2

Input

H 1
He 4
O 16
END_OF_FIRST_PART
H
((H)2He)2
H2O
Xx
0

Expected output

1
12
18
UNKNOWN

Example 3

Input

Na 23
Cl 35
END_OF_FIRST_PART
Na99
(NaCl)2
NaCl
0

Expected output

2277
116
58

Example 4

Input

C 12
Co 59
O 16
END_OF_FIRST_PART
CoO
CO
Co2
0

Expected output

75
28
118

Example 5

Input

H 1
END_OF_FIRST_PART
H2Mg
H
0

Expected output

UNKNOWN
1

Example 6

Input

H 1
O 16
C 12
END_OF_FIRST_PART
((CO2)3H)2
0

Expected output

Example 7

Input

Zz 1000
Q 1
END_OF_FIRST_PART
Zz99
Q99
(QQ)33
0

Expected output

99000
99
66