계좌 잔액 정산하기

ACM 월드 파이널을 마치고 집으로 돌아가는 15명의 대규모 팀에게 큰 고민이 생겼습니다.

지난 몇 주 동안 이들 사이에는 수많은 금전 거래가 있었습니다. 어떤 사람은 다른 사람들의 놀이공원 입장료를 대신 냈고, 또 다른 사람은 호텔 방값을, 누군가는 렌터카 비용을 냈습니다.

이제 큰 정산이 시작됩니다. 어떤 사람은 남들보다 더 많이 냈으므로, 각자의 계좌를 다시 균형 맞춰야 합니다. "누가 누구에게 얼마를 지불해야 하는가?"가 바로 풀어야 할 문제입니다.

이런 계산은 손이 많이 가므로, 내년에도 이 문제를 대신 풀어 줄 프로그램이 필요합니다.

입력은 하나 이상의 테스트 케이스로 이루어집니다.

각 테스트 케이스의 첫 줄에는 두 정수 $n$과 $t$가 주어집니다. $n$은 여행자 수($n \ge 2$), $t$는 거래 수($t \ge 1$)입니다. 이어지는 $n$개의 줄에는 여행자들의 이름이 한 줄에 하나씩 주어집니다. 이름은 알파벳 문자로만 이루어지며 공백을 포함하지 않습니다. 그다음 $t$개의 줄에는 name1 name2 amount 형식으로 거래가 주어지며, 이는 name1이 name2에게 amount 달러를 주었다는 뜻입니다. amount는 항상 $10000$ 미만의 음이 아닌 정수입니다.

$n$과 $t$가 모두 $0$인 줄이 주어지면 입력이 끝납니다.

각 테스트 케이스마다 먼저 Case #i 형식의 줄을 출력합니다. 여기서 $i$는 테스트 케이스 번호이며 $1$부터 시작합니다.

그다음, 모든 여행자의 계좌를 정산하는 거래들을 입력과 같은 name1 name2 amount 형식으로 출력합니다. 이는 name1이 name2에게 amount 달러를 지불한다는 뜻입니다. 금액은 음수가 될 수 없습니다. 음수 금액을 출력하는 대신 두 이름의 순서를 바꾸어 출력하세요.

유효한 정산 방법은 여러 가지일 수 있으므로, 답이 유일하도록 다음의 표준(canonical) 정산을 출력합니다. 입력에 이름이 나열된 순서대로 여행자에게 $1, 2, \dots, n$의 번호를 매기고, 여행자 $k$의 순수 잔액을 다음과 같이 정의합니다.

$$b_k = (k\text{가 받은 총액}) - (k\text{가 준 총액})$$

이 값은 입력의 모든 거래를 반영합니다. 그리고 $i = 1$부터 $n-1$까지 각각에 대해 접두합 $S_i = b_1 + b_2 + \dots + b_i$를 구한 뒤 다음과 같이 출력합니다.

• $S_i > 0$이면 여행자 $i$가 여행자 $i+1$에게 지불합니다: 여행자 $i$의 이름, 여행자 $i+1$의 이름, 그리고 $S_i$를 출력합니다.
• $S_i < 0$이면 여행자 $i+1$이 여행자 $i$에게 지불합니다: 여행자 $i+1$의 이름, 여행자 $i$의 이름, 그리고 $-S_i$를 출력합니다.
• $S_i = 0$이면 이 쌍에 대해서는 아무것도 출력하지 않습니다.

이 거래들을 $i$가 증가하는 순서로 출력합니다. 이렇게 하면 거래 수는 최대 $n-1$개가 됩니다. 마지막으로, 각 테스트 케이스 뒤에는 (마지막 케이스 뒤에도) 빈 줄을 하나 출력합니다.