2013年7月23日 星期二

196 - Spreadsheet


在 1979 年,Dan Bricklin 和 Bob Frankston 撰寫了 VisiCalc 這套電腦程式,是第一款的電子試算表(就如同 Excel)的運用,在當時是個相當大的成功,號稱是 Apple II 電腦的殺手應用軟體。現今,電子試算表(spreadsheets)仍可以在很多電腦中找到。


電子試算表的想法非常簡單,但卻相當強大。試算表的每格會有一個數值或者是公式,公式可以藉由表示法以及其他表格的數值計算得到,而文字和圖形可以用來輔助說明。


你可以寫一個簡單的試算表應用,程式會接到幾組試算表,每格會有整數數值或者是公式表示,公式中只會有計算總和,請計算所有表格中的數值,並且輸出。

由左而右開始命名每一列(column)。


Input

輸入第一行會有一個整數,表示皆下來有多少組測資。

每組測資第一行會有兩個整數 column, row ,而接下來會有 row 行,每行上會有 column個訊息,表示該格的數值或者是公式。

公式表示法為:一個等號(=)接著有數個格子的編號,以加號(+)分隔。藉此計算該格的數值。

需要去找那格的數值出來進行加總,找的時候可能也會遇到公式表示的格子。公式表示法中不會有任何的空白。

保證測資中,不會有任何環狀不可解的情況,每一個都是可以被計算出來的。

格式的命名方式,先用字母表示 column,緊接著是一個整數(範圍從 1 - 999)表示 row
而字母的順序為:A, B, C, ..., Z, AA, AB, AC, ..., AZ, BA, ..., BZ, CA, ..., ZZ, AAA, AAB, ..., AAZ, ABA, ..., ABZ, ACA, ..., ZZZ,依序對照整數 1 到 18278。例如左上角的格子即為 A1

Output

對於每組測資,輸出 row x column 的表格。

Sample Input

1
4 3
10 34 37 =A1+B1+C1
40 17 34 =A2+B2+C2
=A1+A2 =B1+B2 =C1+C2 =D1+D2

Sample Output

10 34 37 81
40 17 34 91
50 51 71 172