Under construction

Still being built. Things may change

Robot Roll Call

Interview

Time limit1sMemory limit128 MB

Summary
Given a roster of names and a multi-line data stream split on spaces and tabs, report for each roster name whether it appears as an exact token.
Level

Easy3 of 10

Topics
Hash map, String, Implementation, Brute force
Solved
No attempts yet

Problem

Robot Roll Call is about to begin. Following the roster received from Earth, the name of each robot is called out, and if a robot is present it responds by adding its own name to a data stream, which is later relayed back to Earth.

Unfortunately, today communication with Earth is temporarily lost right after the roster arrives. In the meantime the robots present for roll call save their names to the data stream, but lots of other data is saved to the same stream as well. To make the data easy to extract later, every piece of data placed in the stream is separated by whitespace.

Your task is as follows. Given a roll-call roster, scan the accompanying data stream and decide whether each name is present in it. For every name in the roster, report whether or not that name appeared in the data stream. For a name to count as a match it must appear exactly as written in the roster: matching is case-sensitive, and substring matches are not allowed.

Input

The first line contains an integer tt (t>0t > 0), the number of test sets in the input. It is followed by tt test sets.

Each test set starts with an integer nn (0<n<260 < n < 26), the number of names in the roster. The next nn lines each contain one roster name. Each name has at most 25 characters and consists only of the characters A–Z, a–z, and 0–9. Names are unique.

After the names comes an integer dd (0<d<1000 < d < 100), the number of lines in the data stream. Each of the following lines holds the characters of the data stream. Every line has at least 1 and at most 100 characters, and the data on a line is separated by whitespace (spaces, tabs, or a combination of the two). Any roster name that appears in the data stream is found within a single line; a name is never split across lines.

Output

For each test set, first print the test-set number (starting at 1) on its own line in the form Test set X:. Then, for each name in roster order, print on its own line <name> is present if the name was found in the data stream, or <name> is absent otherwise.

Separate the outputs of two consecutive test sets with a single blank line.

Examples1

  1. Example 1

    Input
    2
    4
    Gypsy
    TomServo
    CrowTRobot
    Cambot
    2
    Manos Torgo Joel 101010 Gypsy tomservo
    Fugitive Alien Time of the Apes crowTrobot Cambot
    2
    R2D2
    C3PO
    1
    Boba Fett c3Po R2D22 Jar Jar Binks Luke give in to the dark side
    
    Expected output
    Test set 1:
    Gypsy is present
    TomServo is absent
    CrowTRobot is absent
    Cambot is present
    
    Test set 2:
    R2D2 is absent
    C3PO is absent