시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 45 5 5 20.833%

문제

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, AC, ..., AZ, BA, ..., BZ, CA, ... ZZ, AAA, AAB, AAC, ... AAZ, ABA, ..., ABZ, ACA, ..., ZZZ 로 문자가 매겨져 있다. 가장 왼쪽 위의 칸 번호는 A1이다.

각 칸에 적혀있는 수는 절대값이 100,000보다 작거나 같은 정수이며, 수식의 값이 231-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

힌트