Spreadsheet Calculator

Time limit1sMemory limit512 MB

Summary

Compute the value of every cell in a spreadsheet where cells hold either a non-negative number or a sum formula referring to other cell addresses, with no circular references.

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

Problem

Write a simple spreadsheet calculator. A spreadsheet is a table of cells arranged in rows and columns.

Every cell of the table holds either a number or a formula. A formula starts with the character = followed by one or more cell addresses. Consecutive addresses are separated by the character +. A formula contains no spaces at all. The value of a cell that holds a formula is the sum of the values of the cells listed in that formula.

A cell address is a column name followed immediately by a row number, with no space between them. The column names are A, B, C, ..., Z, AA, AB, AC, ..., AZ, BA, BB, BC, ..., BZ, CA, CB, CC, ..., CV, and in that order they stand for columns 1 through 100. Rows are numbered 1 through 100.

Input

The first line contains two integers $R$ and $S$ ( $1 \le R \le 100$ , $1 \le S \le 100$ ). $R$ is the number of rows and $S$ is the number of columns of the table.

Each of the next $R$ lines contains the contents of the $S$ cells in that row. The contents of one cell is either a non-negative integer at most 100, or a formula with at most 10 addends (cell addresses).

The input never contains a circular reference between cells.

Output

Print $R$ lines. Each line contains the values of the $S$ cells in that row, separated by single spaces. Every value is smaller than $2^{31}$ .

Examples3

Example 1
Input
```
2 2
1 =B2+A2
3 5
```
Expected output
```
1 8
3 5
```

Example 2

Input

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

Expected output

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

Example 3

Input

5 4
11 =A5+A3+D5+C4+B2 2 =D4+C4+A1+B4
=B3+C4 5 =A2+D5 5
=B3 13 9 =C5+C3+C1+A1+B1
2 14 9 =B2+D5+C3
=C5+B5+D2+D2 =B3 3 =A4+A1+B2+B4

Expected output

11 85 2 80
22 5 54 5
13 13 9 110
2 14 9 46
26 13 3 32