IPCELLS - Cells

Tim loves spreadsheets. Everything he does on a computer, he does in a spreadsheet. Track his expenses? Create a spreadsheet! Decide which car to buy? Create a spreadsheet to compare them! Make an inventory of his games? Create a spreadsheet! Decide which girl he loves most? …

Unfortunately his spreadsheet software just crashed and he needs some of the data right now and does not have the time to install a competing office suit.

Given the formulas used in the cells of a spreadsheet, calculate the values of all the cells.

Input

The first line of the input file contains an integer T specifying the number of test cases. Each test case is preceded by a blank line.

Each test case starts a single number N giving the number of expression. Each of the following N lines contains a single cell formula of the form “CELL = EXPRESSION”, where CELL is the name of the cell and EXPRESSION is a mathematical expression consisting of cell names and the operators +, -, * and /. A cell name is a non-empty sequence of letters followed by a positive integer.

Each test case is correct: there are no cycles, and all cells referenced in expressions have definitions.

Evaluating expressions

When evaluating an expression, usual priorities apply: first we evaluate all * and / (left to right), and only then all + and - (again, left to right).

You may assume that the expressions are such that when evaluating the expression in correct order, the result and also all intermediate values will fit into 32-bit signed integer variables.

The operator / represents integer division which is always rounded down. The dividend will always be non-negative and the divisor will always be positive.

Output

For each test case output the calculated values of cells, one per line, in the form “CELL = VALUE”. The rows in the output should be ordered alphabetically. (To compare two rows, take a look at the first character where they differ. The one with a smaller ASCII value goes first.)

Optionally, output a blank line between test cases.

Example

Input:
2

3
A47 = 5 + ZZ22
ZZ22 = 3
A9 = 13 + A47 * ZZ22

2
A1 = 4 / 7 + 4 / 7
B2 = 3 * 3 / 7 Output: A47 = 8
A9 = 37
ZZ22 = 3

A1 = 0
B2 = 1

Added by:Mohammad Kotb
Date:2010-08-27
Time limit:1.002s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: OBJC VB.NET
Resource:IPSC

hide comments
2022-07-15 23:25:48 vas14
Just FYI, within the expressions, operators/cell names/numbers are separated by whitespace (as in makes for easy parsing of expressions).

Last edit: 2022-07-15 23:26:23
2021-09-11 04:09:41 David
Problem statement says: EXPRESSION is a mathematical expression consisting of cell names and the operators +, -, * and /.
Correction: EXPRESSION is a mathematical expression consisting of cell names, integers, and the operators +, -, * and /.

An EXPRESSION (as shown in the examples) may contain integers.

Last edit: 2021-09-11 04:11:43
2018-10-05 23:38:25 :D
Some clarifications:
In my AC solution I assumed there is exactly one definition for every cell.
Field "A1" would come before field "AA1" in the output.
2011-04-20 20:37:54 Parag gupta
can a cell appear on the left side more than once ? means can a cell has two definition but both evaluate same ?
2010-09-07 21:13:15 যোবায়ের
Why don't you add the constraints in the problem statement? Many people never read comments. Thanks.
2010-08-28 20:06:22 numerix
If you have solved this, you may try TFRACAL2.
2010-08-27 16:04:27 Mohammad Kotb
T <= 200, N <= 500
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.