cho.sh

Spreadsheet Calculator

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.

Medium5GraphDFSImplementationNo attempts yetTime limit1sMemory limit512 MB

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 RR and SS (1≤R≤1001 \le R \le 100, 1≤S≤1001 \le S \le 100). RR is the number of rows and SS is the number of columns of the table.

Each of the next RR lines contains the contents of the SS 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 RR lines. Each line contains the values of the SS cells in that row, separated by single spaces. Every value is smaller than 2312^{31}.