Spreadsheet Formulas

A spreadsheet works out every cell from what was typed into the cells. Write evaluate(cells) for a tiny one. cells is a dictionary from cell names to what was typed in them, and the result is a dictionary with the same keys, in the same order, holding each cell's value.

• A cell name is a capital letter A to Z followed by a row number from 1 to 999, such as A1 or C12.
• A cell whose text does not start with = holds an integer, such as '42' or '-7'.
• A cell whose text starts with = holds a formula made of whole numbers, cell names, +, -, * and parentheses, with any spaces between them. * is worked out before + and -, and operators of equal priority go from left to right. A - may also stand in front of a number, a cell name or a bracket to negate it, as in =-A1 or =2*-3.

Some cells cannot be worked out:

• A cell that can reach a cycle by following references (a formula names a cell, whose formula names another, and so on) gets the string '#CYCLE'. This includes every cell on the cycle itself, such as A1 holding =B1 while B1 holds =A1, or a cell that names itself.
• Otherwise, a cell that names a cell missing from cells, or can reach such a name by following references, gets the string '#REF'.

Every other cell's value is an int.

Examples

evaluate({'A1': '5', 'A2': '=A1*2', 'B1': '=A1 + A2*3'})
# returns {'A1': 5, 'A2': 10, 'B1': 35}
evaluate({'A1': '=B1+1', 'B1': '=A1*2', 'C1': '7', 'C2': '=C1-A1'})
# returns {'A1': '#CYCLE', 'B1': '#CYCLE', 'C1': 7, 'C2': '#CYCLE'}
evaluate({'A1': '=Z9+1', 'A2': '=(A1 - 3) * 2', 'A3': '=-4 * (2 + 3)'})
# returns {'A1': '#REF', 'A2': '#REF', 'A3': -20}

A cell that can reach both a cycle and a missing cell is '#CYCLE'.

Constraints

• cells has at most 26,000 entries. Every formula is well formed and at most 200 characters long.
• A chain of references through different cells is at most 100 cells long.
• Values can grow very large, which Python's integers handle.