Categorize Expenses

You are given a list of expenses and a set of categories with associated keywords. Each expense record consists of an amount and a description. For each expense, your task is to determine the first category (in the given order) whose keywords appear as a substring in the expense's description. If no keyword is found in any category, assign the category "Uncategorized".

The input is read from standard input. First you are given an integer N representing the number of expenses, followed by N lines, each containing an expense record where the first token is the amount (an integer) and the rest of the line is the expense description. Then, an integer M is given, representing the number of categories. This is followed by M lines. Each category line starts with the category name, then an integer K representing the number of keywords, and finally K keywords separated by spaces.

For each expense, output a line to standard output containing the description followed by a colon, a space, and the assigned category.

Note: If multiple categories match, choose the one that appears first in the input order. Formally, if we let \(C_1, C_2, \dots, C_M\) be the categories in order, then the assigned category for an expense description \(d\) is:

[ \text{category}(d)=\begin{cases} C_i & \text{if } \exists, i \text{ such that } \exists, keyword \in C_i \text{ with } keyword \subset d \text{ and for all } j < i, \forall, keyword' \not\subset d,\ \text{Uncategorized} & \text{if no such category exists.} \end{cases} ]

inputFormat

The first line contains an integer N indicating the number of expenses.

The next N lines each contain an expense record. Each record starts with an integer denoting the amount, followed by the expense description (which may contain spaces).

The following line contains an integer M indicating the number of categories.

Each of the next M lines describes a category with the following format:

CategoryName K keyword1 keyword2 ... keywordK

outputFormat

For each expense, output a single line to stdout containing the expense description, followed by a colon, a space, and the assigned category.

## sample

3
150 grocery shopping at Walmart
200 monthly rent
50 subway sandwich
2
Food 3 grocery subway restaurant
Housing 2 rent mortgage

grocery shopping at Walmart: Food
deal: uncategorized

</p>