Programming Puzzles

Spreadsheet Calculator
A spreadsheet is a rectangular array of cells. All cells contain data or expressions that can be evaluated to obtain data. A simple spreadsheet is one in which all data are positive integers and expressions contains only the operators + (addition), - (subtraction), * (multiplication) and cell references. You may assume that normal order of precedence operates. In addition, the expression SUM(XI:XJ) which means sum of the values for the cells in the range XI to XJ is also valid. For example SUM(A1:A3) means A1+A2+A3, and SUM(B3:D3) means B3+C3+D3, i.e. SUM is a function which operates on cells within a range in either a column or a row. For an expression, if each cell referenced contains an integer, then the expression can be replaced by the integer to which the expression evaluates. You are to write a program which evaluates a series of simple spreadsheets. You may assume that there are no cases of self or cyclic cell references.

Input
The input consists of a sequence of simple spreadsheets. Each spreadsheet begins with a line specifying the number of rows and the number of columns. No spreadsheet contains more than 14 rows or 10 columns. Rows are labelled by capital letters A through to N, and columns are labelled by decimal digits 0 through to 9. Hence the cell in the first row and first column is A0 and in the tenth row and fifth column is J4.

Following the specification of the number of rows and columns is one line of data for each cell, in row major order (i.e. cells for first row, followed by cells for second row, etc.). Each cell initially contains a positive integer or an expression. No expression contains more than 75 characters.

The end of the sequence of spreadsheets consists of a single line specifying 0 rows and 0 columns

Output
For each spreadsheet in the input, you are to determine the value of each expression and display the resulting spreadsheet, which includes those cells which had initially integers, on a rectangular array of numbers with rows and columns appropriately labelled. You may assume that the input and evaluated values in the cells will be between the limits -9000 and 10000.

Sample input

6 4
20
30
40
SUM(A0:A2)
A0*2
3*A1
10
20
A1-A0
A1*5
5
10
2
4
6
8
A0*D0
A1*D0+D3
12
24
5
8
SUM(A2:E2)
100
0 0

Sample Output