Daily Product Recommendation

You are given a list of products along with their popularity scores and associated categories. The first line of the input consists of two integers n and k where n is the number of products and k is the maximum number of recommendations per category. The following n lines each contain details of a product: its name, a positive integer popularity score, and one or more categories that the product belongs to. The list is terminated by a line containing the word end.

For each category, you are required to recommend at most k products. However, across all categories, a product can be recommended no more than twice. For each category, the recommended products are selected by sorting the products in that category by their scores in descending order. In case of ties, the product that appeared earlier in the input is given precedence. Finally, the output should list each category (in alphabetical order) followed by the recommended products for that category.

The problem thus requires you to implement the recommendation logic under the given constraints and produce the corresponding output.

inputFormat

The input is read from standard input. The first line contains two integers separated by a space: n (the number of products) and k (the maximum recommendations per category). This is followed by n lines, each describing a product in the following format:

product_name score category1 category2 ...

The final line of the input is a single word: end.

outputFormat

The output is written to standard output. For each category (sorted alphabetically), output a line in the format:

category: product1 product2 ...

Each category line lists the recommended products (up to k) subject to the constraint that no product is recommended more than twice overall.

## sample

6 3
product1 500 electronics children
product2 800 electronics
product3 600 sports
product4 700 sports electronics
product5 750 children
product6 650 children sports
end

children: product5 product6 product1
electronics: product2 product4 product1
sports: product4 product6 product3

</p>