Top K Customers by Spending

You are given a list of customer records. Each record consists of a customer ID and their total spending amount. The task is to identify the top k customers with the highest spending. In case of ties (i.e. when multiple customers have the same spending), the customer IDs should be sorted in ascending order.

The sorting criteria can be mathematically represented as follows:

Sort the records by spending in descending order, and if two records have the same spending, sort by customer_id in ascending order. Formally, for two records \(a\) and \(b\), we order \(a\) before \(b\) if:

[ \text{if } a.spending > b.spending \quad \text{or} \quad (a.spending = b.spending \text{ and } a.customer_id < b.customer_id). ]

You need to implement a solution that reads the input from stdin and writes the desired output to stdout.

inputFormat

The first line of input contains two integers n and k, where n is the number of customer records, and k is the number of top customers to select.

The next n lines each contain two integers: the customer_id and the spending amount for that record.

Example:

4 2
4 100
2 200
3 200
1 50

outputFormat

Output a single line containing the k customer IDs of the top customers, separated by a single space. The customers must be ordered first by descending spending and then by ascending customer ID in case of ties.

Example:

2 3

## sample

1 1
1 100

1

</p>