Volleyball Scores

Interview

Time limit1sMemory limit128 MB

Summary

Given a sequence of ball touches, ground hits, and out of bounds calls, compute the volleyball score while checking that the correct team serves each volley.

Level: Medium6 of 10
Topics: Simulation, Implementation, Array
Solved: No attempts yet

Problem

Beach volleyball is a popular game to play at the beach: each side forms a team of two or more players, and the two teams try to hit the ball back and forth.

To keep score seriously, we record the sequence of what happened during play. Your task is to compute the current score from that sequence.

Here is a quick refresher on the rules. Only the serving team can score. If the serving team wins a volley, it earns a point and keeps serving. If the serving team loses a volley, no point is awarded, but the other team serves next. In other words, whichever team wins a volley always serves the next one.

There are several ways to lose a volley:

One of your players touches the ball twice in a row.
Players of your team touch the ball at least four times in a row.
The ball touches the ground in your court.
The ball touches the ground out of bounds, and one of your players was the last to touch it.
One of your players touches the ball immediately after one of your players served it.

Given the sequence of who touched the ball (touching may include serving), determine the current score. If at any moment the wrong team serves, report an error instead.

(We ignore the effect of the net and a few other details, such as the requirement that the server rotate.)

Input

The first line contains an integer $K \ge 1$ , the number of data sets. Each data set has the following form.

The first line of a data set contains three integers $n_1$ , $n_2$ , and $t$ with $2 \le n_1, n_2 \le 10$ and $1 \le t \le 1000$ . Here $n_1$ and $n_2$ are the numbers of players on Team A and Team B (they need not be equal), and $t$ is the length of the sequence of ball touches.

The second line contains a sequence of $t$ ball touches separated by single spaces, where each touch is one of the following:

An integer $i$ with $1 \le i \le n_1 + n_2$ means player $i$ touched the ball (this may be a serve). Players $1, \dots, n_1$ are on Team A, and players $n_1 + 1, \dots, n_1 + n_2$ are on Team B.
The letter A or B means the ball touched the ground in the court of Team A or Team B, respectively.
The letter X means the ball touched the ground out of bounds.

The first ball touch of every sequence is always an integer: the player who serves first. The input never contains impossible sequences, except for wrong serves.

Output

For each data set, first output a line Data Set x:, where $x$ is the data set number. Then output the two teams' scores (Team A first, then Team B) separated by a single space. If at any point during the sequence a player from the wrong team serves, output Wrong Serve instead of the score.

Examples1

Example 1

Input

3
3 3 6
1 2 5 A 4 X
2 2 20
1 3 4 3 1 2 1 2 3 1 2 4 A 4 2 4 1 2 X 3
6 6 5
10 1 2 B 7

Expected output

Data Set 1:
0 1
Data Set 2:
0 2
Data Set 3:
Wrong Serve