Earrings

Interview

Time limit1sMemory limit128 MB

Summary
Given girl names and 2n-1 confiscation/return records tagged with a number and a letter, find the girl whose number appears only once and thus never got her earring back.
Level

Easy2 of 10

Topics
Hash map, Array, Implementation
Solved
No attempts yet

Problem

Many girls at Pascal High School wear earrings that are not allowed by the school rules. Whenever Vice Principal Sneddon sees long, dangling red earrings, he confiscates them.

The vice principal made a numbered list of the girls whose earrings were confiscated. On the back of each confiscated earring, he wrote the girl's number and either A or B, chosen arbitrarily.

After all regular classes and after-school detentions end, the girls visit the vice principal to get their earrings back. Unfortunately, one day he lost the envelope containing the earrings, and one earring could not be found.

Tell the vice principal the name of the angry girl who did not get her earring back.

Input

The input consists of several numbered scenarios. Scenario numbers start at 1 and increase by 1 in input order. Each scenario is given as follows.

  • The first line contains the number n of girls whose earrings were confiscated. (1 ≤ n ≤ 100)
  • The next n lines contain the girls' names, one per line. Each name has length at most 60 characters.
  • The next 2n - 1 lines each contain a girl number and the letter A or B, separated by a space. The number matches the order of the vice principal's list, so 1 means the first girl whose earrings were confiscated. A girl's number appears at most twice, and when it appears a second time, it is paired with the other letter. The first record for a number represents confiscation, and the second record represents return.

A final line containing 0 ends the input. Do not process this line.

Output

For each scenario, output one line containing the scenario number and the name of the girl who did not get her earring back, separated by one space.

Examples1

  1. Example 1

    Input
    3
Betty Boolean
Alison Addaway
Carrie Carryon
1 B
2 A
3 B
3 A
1 A
2
Helen Clark
Margaret Thatcher
1 B
2 B
2 A
0
    Expected output
    1 Alison Addaway
2 Helen Clark