User Activity Categorization

You are given a list of user activities along with a mapping from activities to their corresponding categories. Your task is to categorize each user based on the activities they perform. For each user, consider only those activities that appear in the mapping; activities not present in the mapping should be ignored.

After processing, print the result for each unique user (sorted in lexicographical order by user ID). For each user, display the user ID followed by a colon and the list of categories (also sorted in lexicographical order) associated with that user. If a user has no matching categories, output only the user ID and a colon.

Input is read from stdin and output should be printed to stdout.

inputFormat

The input is given in the following format:

• The first line contains an integer N representing the number of user activity records.
• The next N lines each contain two strings: user_id and activity, separated by space.
• The following line contains an integer M representing the number of mapping entries.
• The next M lines each contain two strings: activity and category, separated by space.

outputFormat

For each unique user (sorted in lexicographical order), output one line in the format:

user_id: category1 category2 ... categoryK

If there are no categories for a user, output the user_id followed by a colon with no categories.

## sample

5
user1 login
user1 purchase
user2 login
user2 logout
user3 login
3
login authentication
purchase transaction
logout authentication

user1: authentication transaction
user2: authentication
user3: authentication

</p>