描述

从前，有一支庞大的队伍从ACM世界总决赛归来。这十五位旅行者面临着一个大问题：

在过去的几周里，他们之间发生了许多金钱交易：有时某人为其他人支付了主题公园的门票，另一个人支付了酒店房间的费用，还有人支付了租车的费用，等等。

于是，现在开始了复杂的计算。一些人比其他人支付了更多的钱，因此需要重新平衡每个人的银行账户。“谁该向谁支付多少钱？”这就是问题的关键。

由于这样的计算非常繁琐，我们需要一个程序来在明年解决这个问题。

输入

输入包含一个或多个测试用例。

每个测试用例的第一行包含两个整数：旅行者数量$n$（$2 \leq n \leq 20$）和交易数量$t$（$1 \leq t \leq 1000$）。接下来的$n$行每行给出一个旅行者的名字。名字仅由少于10个字母字符组成，且不包含空格。接下来的$t$行，每行描述一笔交易，格式为name1 name2 amount，表示name1向name2支付了$amount$美元。$amount$始终是一个非负整数且小于$10000$。

输入以两个$0$（表示$n$和$t$）结束。

输出

对于每个测试用例，首先输出一行Case #i，其中$i$是测试用例的编号。

接着，在接下来的几行中，输出一系列交易，以抵消输入中的交易，即重新平衡账户。使用与输入相同的格式。每个测试用例后输出一个空行，即使是最后一个测试用例。

附加限制条件：

1. 你的解决方案最多只能包含$n-1$笔交易。
2. 金额不能为负数，即不要输出A B -20，而应输出B A 20。
3. 如果有多个满足这些限制的解决方案，输出任意一个即可。

输入样例 1

2 1
Donald
Dagobert
Donald Dagobert 15
4 4
John
Mary
Cindy
Arnold
John Mary 100
John Cindy 200
Cindy Mary 40
Cindy Arnold 150
0 0

输出样例 1

Case #1
Dagobert Donald 15

Case #2
Mary John 140
Cindy John 10
Arnold John 150

来源
Ulm Local 1998