And the Winner Is

Interview

Time limit1sMemory limit128 MB

Summary

Each ballot has one character per candidate; discard any ballot that marks more than one candidate in the same race, then report the top vote-getter (ties included) in every race, in input order.

Level: Medium5 of 10
Topics: Implementation, Array, Hash map, Simulation
Solved: No attempts yet

Problem

After an election we must count the votes each candidate received and determine the winners. We have to be careful, though: voters sometimes fill out their ballots incorrectly, and any such ballot must be discarded. Write a program that correctly determines the winners of the elections.

Why several elections at once? A single ballot usually contains many separate votes — for senator, for congressperson, for district positions, and so on. Here we assume that if the vote for any one of these categories is filled out incorrectly, then the entire ballot is discarded.

Input

The first line contains the number of data sets $K$ ( $K \ge 1$ ) in the file. It is followed by $K$ data sets of the form below.

The first line of a data set contains three integers $n$ , $r$ , and $v$ : the number of candidates ( $1 \le n \le 100$ ), the number of races ( $1 \le r \le 9$ ), and the number of voters ( $1 \le v \le 10000$ ). The next $n$ lines describe the candidates. Each line begins with an integer from $1$ to $9$ giving the race that candidate is running in, followed by a single space and then the candidate's name (a name may contain spaces). Every race has at least one candidate.

The next $v$ lines describe each voter's ballot. Every line is a string of exactly $n$ characters, each either x or #. An x in position $j$ means the voter voted for candidate $j$ , and a # in position $j$ means they did not. If a voter voted for more than one candidate in the same race, the entire ballot is discarded. On the other hand, casting no vote at all in a particular race is fine.

Output

For each data set, first print Data Set x: on a line by itself, where x is its number. Then print the names of all candidates who finished first (or tied for first) in their race, in the order in which they appeared in the input.

Examples5

Example 1

Input

1
5 2 5
1 Jay Bulworth
1 Hugh Waldron
2 USC
2 UCLA
2 CalTech
xx###
x#x##
####x
xx#x#
x####

Expected output

Data Set 1:
Jay Bulworth
USC
CalTech

Example 2
Input
```
1
1 1 1
1 Alice
x
```
Expected output
```
Data Set 1:
Alice
```

Example 3

Input

1
3 1 4
1 Anna
1 Bob
1 Carl
x##
#x#
xx#
###

Expected output

Data Set 1:
Anna
Bob

Example 4

Input

2
2 1 3
1 X
1 Y
x#
x#
#x
1 1 1
1 Solo
x

Expected output

Data Set 1:
X
Data Set 2:
Solo

Example 5

Input

1
4 2 3
1 Red
1 Blue
2 Cat
2 Dog
x#x#
x##x
#x#x

Expected output

Data Set 1:
Red
Dog