Yes it is an address, but it is a long story for a group of Egyptian guys who travelled with each other during their summer internship in US everyone was working in a company and they live together in this apartment. During their life they faced a lot of problems and headache for paying money when they are in a restaurant or paying a bill for the apartment as almost they don't deal with cash money, everyone is working with his credit card to pay everything so it will be a big headache to divide the receipt to pay it with 5 credit cards for example.

So Kabby (one of these guys) has decided to make a shared spreadsheet between all the guys, and in this sheet if anyone paid a bill or a receipt he will insert a new record and how much money he owe for each one of the other guys, and has spent hours to make some scripts in this spreadsheet to show a very simple table to summaries how much everyone owe the other.

So to summarize, every one of the N guys has M bank account, and given all transactions that made between these guys in the format that A has paid from his X bank account an amount T to B in his Y bank account. So Kabby wants to help him to calculate the total credit everyone have in all his accounts given the initial bank accounts balances.

Input

The first line of input contains an integer T that represents the number of test cases. Every following test case will start with a line contains two integers N and M (2 <= N <= 10) number of persons in the apartment and M (1 <= M <= 10) represents the number of bank accounts everyone have, followed by two lines first line contains N space separated lowercase letters strings represents distinct names of the N guys, and the second line contains M space separated lowercase letters strings represents the distinct names of the M banks.

Followed by N * M line that will describe the initial account balances for each person in each bank in the format “name bank x” where name is the guy name, bank is the bank name and x (-1,000 <= x <= 1,000)is the initial account balance.

Then a line contains a single integer Tr (1 <= Tr <= 50) represents the number of transactions, followed by Tr lines on the following format “source_name source_bank dest_name dest_bank amount”, where source_name and source_bank are the name of the guy who will pay and the bank account he will transfer from respectively, while dest_name and dest_bank are the name of the guy who will receive the amount and his bank account name, and finally amount is an non-negative value that will be transferred through the accounts. And it is good to mention that these bank accounts allow negative balances.

Output

For each test case, output a single line in the beginning of the test case in the form “Case #T:” where T is the number of the test case, followed by N lines in the format “name credit” that represents the name of the guy and his total credit value in all of his bank accounts order by alphabetical order of names.

Example

Input:
1
2 2
mk aa
ck sv
mk ck 100
mk sv -10
aa ck 50
aa sv 20
3
mk sv aa sv 10
aa ck mk sv 30
mk ck aa sv 40

Output:
Case #1:
aa 90
mk 70