스프레드시트

시간 제한1초메모리 제한128 MB

요약

각 셀에는 정수 또는 다른 셀들을 더하는 수식이 들어 있다. 순환이 없을 때 모든 수식을 계산해 격자를 그대로 출력한다.

난이도: 보통10점 중 6점
유형: 그래프, 위상 정렬, DFS, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

1979년 댄 브리클린과 밥 프랭스턴은 최초의 스프레드시트 응용 프로그램인 VisiCalc를 만들었다. 이 프로그램은 큰 성공을 거두었고, 애플 II 컴퓨터의 필수 앱이 되었다. 오늘날 스프레드시트는 거의 모든 데스크톱 컴퓨터에 설치되어 있다.

스프레드시트의 핵심 아이디어는 간단하지만 강력하다. 스프레드시트는 표로 이루어져 있고, 표의 각 칸에는 정수 또는 수식이 들어간다. 수식의 값은 다른 칸에 적힌 값을 이용해 계산한다.

이번에는 아주 간단한 스프레드시트 앱을 만들려고 한다. 각 칸에는 정수 또는 수식이 들어가며, 수식은 덧셈(합)만 지원한다. 각 칸에 적힌 정수나 수식이 주어졌을 때, 모든 수식의 값을 계산하는 프로그램을 작성하시오.

각 칸의 이름은 아래와 같이 매겨진다.

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   ...
...  ...  ...  ...  ...  ...  ...

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스의 첫째 줄에는 스프레드시트의 열의 개수 $M$ 과 행의 개수 $N$ 이 주어진다. 이어지는 $N$ 개의 줄에는 스프레드시트의 내용이 한 줄에 한 행씩 주어지며, 한 행의 각 칸은 공백으로 구분된다.

각 칸에는 정수 또는 수식이 적혀 있다. 수식은 =로 시작하고, 그 뒤에 칸의 이름이 +로 구분되어 나열된다. 수식의 값은 그 수식이 가리키는 모든 칸의 값을 더한 것이다. 수식은 다른 수식이 적힌 칸을 가리킬 수도 있으며, 수식 안에는 공백이 없다.

칸이 서로를 가리키는 관계에 사이클은 존재하지 않으므로, 모든 수식은 항상 계산할 수 있다.

칸 이름에서 행은 1부터 999까지의 정수로 나타내고, 열은 A, B, C, …, Z, AA, AB, …, AZ, BA, …, ZZ, AAA, …, ZZZ 순서로 문자로 매겨진다. 각 열은 1번부터 18278번까지에 해당한다. 가장 왼쪽 위 칸의 이름은 A1이다.

각 칸에 적힌 수는 절댓값이 100,000 이하인 정수이고, 어떤 수식의 값도 $2^{31}-1$ 을 넘지 않는다. 또한 각 테스트 케이스에서 전체 칸의 개수는 1,700,000개를 넘지 않고, 수식이 다른 칸을 가리키는 총 횟수는 250,000번을 넘지 않는다.

출력

각 테스트 케이스마다 모든 수식을 계산한 뒤, 스프레드시트의 내용을 입력과 같은 형식으로 출력한다. 각 행의 칸은 공백으로 구분한다.

예제3

예제 1

입력

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

예상 출력

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

예제 2
입력
```
1
1 1
42
```
예상 출력
```
42
```
예제 3
입력
```
1
3 1
-5 10 =A1+B1
```
예상 출력
```
-5 10 5
```