Spreadsheet

Interview

Time limit1sMemory limit128 MB

Summary

Evaluate a small 9x26 spreadsheet where each cell holds an integer expression with +, -, *, / and cell references, reporting 1000000 if cell A1 is part of a circular reference.

Level: Medium6 of 10
Topics: Implementation, DFS, Recursion, Graph
Solved: No attempts yet

Problem

Write a program that emulates a very simple spreadsheet. The sheet has 9 rows (numbered 1 to 9) and 26 columns (labeled A to Z). A cell is referenced by its column letter followed by its row number, for example B1 or S8.

Each cell holds an expression of at most 255 characters. Expressions are built from integer constants, cell references, parentheses, and the operators +, -, *, and / (whole division). For example, 567, E8/2, and (3+B3)*(C4-1) are all valid expressions.

All operations are on integers. Whole division truncates toward zero (for example 7/2 = 3 and (0-7)/2 = -3), and division by zero yields 0. Every operand and every result is guaranteed to have absolute value less than 1000000, so the value 1000000 is reserved to signal a circular reference.

If a referenced cell has no expression of its own, its value is taken to be 0. When two or more cells depend on one another, directly or indirectly, that is a circular reference.

Input

The first line contains the number of expressions N. Each of the next N lines has the form <cell reference>=<expression>. Every expression is syntactically valid, and each cell is defined by at most one expression. Whitespace may appear around tokens.

Output

Print a single line containing the value of cell A1, or 1000000 if A1 cannot be computed because of a circular reference.

Examples3

Example 1

Input

4
A1=B1+C5
B1=20
C5 =B1 /D7-E1*E1
E1=(3+1)*2

Expected output

-44

Example 2
Input
```
1
A1=42
```
Expected output
```
42
```
Example 3
Input
```
1
B1=5
```
Expected output
```
0
```