gRanks

세계에는 뛰어난 선수가 많다. 대회마다 우승자가 다르면 누가 가장 잘하는지 말하기 어렵다. 선수의 순위를 매기는 한 가지 방법은 다음과 같다.

1. 점수를 주는 상위 등수의 개수 $P$와 $i$등에게 주는 점수 $S_i$를 정한다. 예를 들어 $P = 3$일 때 1등에게 1000점, 2등에게 500점, 3등에게 300점을 주고 그 아래 등수에는 0점을 주기로 할 수 있다. 한 대회 안에서 공동 등수는 없다.
2. 대회의 중요도가 모두 같지는 않으므로 $i$번째 대회에 가중치 $W_i$를 부여한다. 한 선수가 그 대회에서 얻는 점수는 1번에서 정한 점수에 그 대회의 가중치를 곱한 값이다. 예를 들어 올림픽의 가중치를 5로 정했다면 위 예에서 올림픽 우승자는 $5 \times 1000 = 5000$점을 얻는다.
3. 대회에 많이 나갔다는 이유만으로 점수가 높아지지 않도록, 한 선수가 모든 대회에서 얻은 점수 가운데 가장 높은 $M$개만 합산한다. 예를 들어 $M = 2$이고 어떤 선수가 세 대회에서 각각 $1000 \times 5$, $500 \times 1$, $300 \times 3$점을 얻었다면 5000과 900만 더해 5900점이 된다.

등수별 점수, 각 대회의 가중치, 대회 결과가 주어진다. 대회에 등장한 모든 선수의 순위를 매겨라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어지며, 각 테스트 케이스는 다음과 같이 이루어진다.

1. 첫 줄에 점수를 주는 상위 등수의 개수 $P$.
2. 둘째 줄에 1등부터 차례로 $P$개의 점수 $S_1, S_2, \dots, S_P$.
3. 셋째 줄에 대회의 수 $N$.
4. 다음 $N$개 줄에 각각 대회 하나의 결과. 각 줄은 그 대회의 가중치 $W_i$로 시작하고, 이어서 상위 $P$등에 든 선수의 이름이 1등부터 차례로 주어진다.
5. 마지막 줄에 한 선수의 점수에 합산되는 대회의 최대 개수 $M$.

각 테스트 케이스마다 먼저 Case #x:를 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이다. 그다음 입력에 등장한 모든 선수를 순위가 높은 쪽부터 한 줄에 한 명씩 r: name 형식으로 출력한다. $r$은 그 선수의 순위이고 name은 이름이다.

합산 점수가 같은 선수는 같은 순위를 공유한다. 한 선수의 순위는 그 선수보다 합산 점수가 높은 선수의 수에 1을 더한 값이다. 순위가 같은 선수는 이름의 사전순으로 출력한다.

• $1 \le T \le 10$
• $1 \le P \le 100$
• $1 \le N \le 100$
• $1 \le M \le 100$
• $1 \le S_i \le 1000$
• $S_i > S_{i+1}$
• $1 \le W_i \le 1000$
• 이름은 알파벳 대문자 A부터 Z까지로만 이루어지고 길이가 10자 이하이다.
• 한 대회의 결과에 같은 이름이 두 번 나오지 않는다.

첫 번째 예제에서 BOLT는 두 대회에서 합계 7000점을 얻었다. GAY는 네 대회의 점수를 모두 더하면 8500점이지만 상위 2개만 세므로 6500점이 되어 2위이다. PEIMENG과 TIANBING은 둘 다 1500점이라 공동 3위이고 이름의 사전순으로 출력된다. LARRY는 1000점뿐이라 마지막이다.