Spreadsheet

Time limit1sMemory limit128 MB

Summary

Each cell holds an integer or a sum formula referring to other cells; evaluate all formulas and print the resulting grid, with no reference cycles.

Level: Medium6 of 10
Topics: Graph, Topological sort, DFS, Simulation
Solved: No attempts yet

Problem

In 1979, Dan Bricklin and Bob Frankston created VisiCalc, the first spreadsheet application. The program was a huge success and became a must-have app for the Apple II. Today, spreadsheets are installed on almost every desktop computer.

The core idea of a spreadsheet is simple but powerful. A spreadsheet is a table in which every cell holds either an integer or a formula. The value of a formula is computed from the values written in other cells.

This time we will build a very simple spreadsheet app. Each cell holds an integer or a formula, and a formula supports only addition (a sum). Given the integer or formula written in each cell, write a program that evaluates every formula.

Each cell is named as follows.

A1   B1   C1   D1   E1   F1   ...
A2   B2   C2   D2   E2   F2   ...
A3   B3   C3   D3   E3   F3   ...
A4   B4   C4   D4   E4   F4   ...
A5   B5   C5   D5   E5   F5   ...
A6   B6   C6   D6   E6   F6   ...
...  ...  ...  ...  ...  ...  ...

Input

The first line contains the number of test cases.

The first line of each test case contains the number of columns $M$ and the number of rows $N$ of the spreadsheet. The next $N$ lines describe the spreadsheet, one row per line; within a row, the cells are separated by spaces.

Each cell contains either an integer or a formula. A formula starts with =, followed by cell names separated by +. The value of a formula is the sum of the values of all the cells it refers to. A formula may refer to a cell that also contains a formula, and a formula contains no spaces.

The reference relationships never form a cycle, so every formula can always be evaluated.

In a cell name, the row is an integer from 1 to 999, and the column is labeled with letters in the order A, B, C, …, Z, AA, AB, …, AZ, BA, …, ZZ, AAA, …, ZZZ. Each column corresponds to a number from 1 to 18278. The name of the top-left cell is A1.

Each integer written in a cell has absolute value at most 100,000, and no formula's value ever exceeds $2^{31}-1$ . Also, within each test case the total number of cells does not exceed 1,700,000, and the total number of times formulas refer to other cells does not exceed 250,000.

Output

For each test case, evaluate every formula and print the spreadsheet in the same format as the input, with the cells of each row separated by spaces.

Examples3

Example 1

Input

1
4 3
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 2
Input
```
1
1 1
42
```
Expected output
```
42
```
Example 3
Input
```
1
3 1
-5 10 =A1+B1
```
Expected output
```
-5 10 5
```