Squirrel
In the enchanted forest, magical trees grow, each with a unique name to facilitate communication without unnecessary disturbance.
Within these magical trees, enchanted hollows house magical squirrels. Each hollow is numbered, with higher numbers indicating higher positions. To ensure the squirrels don't lose their way, a wise owl provides each with a magical slip of paper detailing its address, which includes the tree's name and the hollow number. The owl also keeps a record of all squirrel addresses in her magical notebook.
Occasionally, new squirrels arrive in the forest, seeking their own hollows. Each has already chosen a tree but may find some hollows occupied. In such cases, the squirrel consults the wise owl to find an available hollow in the chosen tree. Being lazy, the squirrels prefer the lowest available hollow. Fortunately, each magical tree has an unlimited number of hollows, each at a different height. Your task is to assist the owl in selecting a hollow for each new squirrel.
Input
The first line contains the number n—the number of entries in the owl's notebook. The next n lines list these entries, each consisting of the concatenation of a tree's name and the hollow number where a squirrel resides. A tree's name is composed of a natural number followed by lowercase Latin letters, and the hollow number is a natural number up to 10^9.
The subsequent line indicates the number of new squirrels. The following lines specify the tree each squirrel wishes to inhabit. The input file size does not exceed 10^6 bytes.
Output
For each squirrel, output the number of the lowest hollow available for settlement.