Product Recommendation System

You are given three integers \(N\), \(M\), and \(K\), where \(N\) is the number of products, \(M\) is the number of purchase records, and \(K\) is the number of recommendations to generate for each user.

Each of the following \(M\) lines contains two integers representing a purchase record in the format: user_id product_id. You must compute, for every user that has made at least one purchase, the top \(K\) most frequently purchased products. If a user purchased fewer than \(K\) distinct products, output all of them.

The products for each user should be sorted according to the following criteria:

• Primarily by descending purchase frequency.
• If two products have the same frequency, by ascending product ID.

The output should list the recommendations for each user (in ascending order of user IDs) on separate lines. Each line contains the recommended product IDs as space-separated values.

inputFormat

The input is read from standard input (stdin) and has the following format:

N M K
user_1 product_1
user_2 product_2
... 
user_M product_M

Where:

• \(N\): Number of products.
• \(M\): Number of purchase records.
• \(K\): Number of recommendations per user.
• Each of the next \(M\) lines contains two integers: the user ID and the product ID.

outputFormat

The output is written to standard output (stdout). For each user (in ascending order of user IDs who made a purchase), output a single line containing the top \(K\) product IDs recommended for that user. The product IDs are space-separated. If a user has no purchase records, output nothing for that user.

## sample

5 6 3
1 2
1 3
2 3
2 4
3 2
3 4

2 3
3 4
2 4

</p>