Problem 1004: Election

(ACM S.E. U.S.A. Regional 2003, problem 4)

Description

The Election and Recall Accounting Unit (ERAU) is holding an election with many candidates and has decided it would be unfair to list the candidates alphabetically, since candidates earlier in the alphabet would be earlier on the ballot. Instead, they've adopted the following listing strategy.

The candidate names will be ordered lexicographically based on the order of the letters A through Z. The order of the letters is not the usual order, but a randomly generated one. One such order of the letters might be R, W, Q, O, J, M, V, A, H, B, S, G, Z, X, N, T, C, I, E, K, U, P, D, Y, F, L. Using this ordering, the name ROBERT would come before JOHN (since R is earlier in the new alphabet than J) and RHONDA would come before REBECCA (since H is earlier in the new alphabet than E).

The new alphabetical listing would be used for District 1. But, in District 2, the first candidate would be moved to the end of the list and the others would move up one spot in the listing. Similarly, in District 3, the first candidate in District 2 would be moved to the end of the list, and the others would be moved up. This pattern of moving the first candidate to the bottom of the list would continue in all districts. So, if the candidates were ROBERT, JOHN, RHONDA, and REBECCA, they would appear on the ballots in the order given:
         District 1: ROBERT, RHONDA, REBECCA, JOHN
         District 2: RHONDA, REBECCA, JOHN, ROBERT
         District 3: REBECCA, JOHN, ROBERT, RHONDA
         District 4: JOHN, ROBERT, RHONDA, REBECCA
         District 5: ROBERT, RHONDA, REBECCA, JOHN
To assist voters in finding their choice, ERAU wants you to write a program to tell voters where to find their candidates. You will be given the new alphabet, a list of candidates, and then a list of candidate-district pairs, and you have to tell where on the ballot in the given district the candidate appears.

Input Format

The input to this program will begin with a line of 26 uppercase letters, representing the new alphabet. Each letter will appear exactly one time.

The next section will list the candidates. The first line will contain a single, non-negative integer, c, 1 <= c <=1000 , representing the number of candidates. There will then be c lines, each with a candidate's name consisting of 1 to 80 uppercase characters. No two candidates will have the same name.

The last section will consist of names the voters want to find (again, 1 to 80 uppercase characters), a semicolon, and an integer, being the district of the voter. The last name in the file will have district 0 and should not be processed.

Output Format

For each name in the last section of input, tell which position the name will be in on the ballot of the given district. The first position is position number 1. If a name is not in the list of names, you should print a message that the name is not on the ballot. Use the wording and formatting in the sample output.

Sample Input

RWQOJMVAHBSGZXNTCIEKUPDYFL
4
ROBERT
JOHN
RHONDA
REBECCA
JOHN;1
REBECCA;3
ARNOLD;2
ROBERT;21562
SCHWARZENEGGER;0

Sample Output

District 1: JOHN is candidate 4
District 3: REBECCA is candidate 1
District 2: ARNOLD is not on the ballot
District 21562: ROBERT is candidate 4