만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

표 계산기

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

요약
스프레드시트의 각 셀은 음이 아닌 정수이거나 다른 셀 주소들의 합을 나타내는 수식이며, 순환 참조가 없을 때 모든 셀의 값을 계산한다.
난이도

보통10점 중 5점

유형
그래프, DFS, 구현
정답자
아직 제출이 없습니다

문제

간단한 표 계산기를 만들자. 표 계산기는 행과 열로 나뉜 칸으로 이루어진 표이다.

표의 각 칸에는 수가 들어 있거나 수식이 들어 있다. 수식은 = 로 시작하고, 그 뒤에 칸의 주소가 하나 이상 이어진다. 주소와 주소는 + 로 구분한다. 수식 안에는 공백이 하나도 없다. 수식이 들어 있는 칸의 값은 그 수식에 적힌 칸의 값을 모두 더한 값이다.

칸의 주소는 열 이름 뒤에 행 번호를 공백 없이 붙여서 쓴다. 열 이름은 A, B, C, ..., Z, AA, AB, AC, ..., AZ, BA, BB, BC, ..., BZ, CA, CB, CC, ..., CV 순서이고, 차례대로 1번 열부터 100번 열을 나타낸다. 행은 1번부터 100번까지 번호로 나타낸다.

입력

첫째 줄에 정수 RR과 SS가 주어진다 (1≤R≤1001 \le R \le 100, 1≤S≤1001 \le S \le 100). RR은 표의 행 개수, SS는 열 개수이다.

다음 RR개의 줄에는 각 줄마다 그 행에 있는 칸 SS개의 내용이 주어진다. 한 칸의 내용은 100 이하의 음이 아닌 정수이거나, 더하는 항(칸 주소)이 최대 10개인 수식이다.

입력에서 칸이 서로 순환 참조하는 경우는 없다.

출력

RR개의 줄을 출력한다. 각 줄에는 그 행에 있는 칸 SS개의 값을 공백 하나로 구분해 출력한다. 모든 값은 2312^{31}보다 작다.

예제3

  1. 예제 1

    입력
    2 2
    1 =B2+A2
    3 5
    
    예상 출력
    1 8
    3 5
    
  2. 예제 2

    입력
    3 4
    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
    
  3. 예제 3

    입력
    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
    
    예상 출력
    11 85 2 80
    22 5 54 5
    13 13 9 110
    2 14 9 46
    26 13 3 32