Citizen Permit Issuance

You are given a list of n citizens and a number k representing the number of permits to issue. Each citizen is described by two integers: their unique id and the number of years they have lived in the town. The permits are issued based on the following criteria:

• Citizens who have lived longer in the town have higher priority.
• If two or more citizens have lived the same number of years, the citizen with the smaller id is given priority.

Your task is to output the ids of the selected citizens in order according to these rules.

In mathematical terms, if we denote the number of years by \(y\) and the citizen id by \(\text{id}\), then the sorting order is defined by sorting on \( -y \) (descending) and then on \( \text{id} \) (ascending).

inputFormat

The input is given via stdin in the following format:

n k
id1 years1
id2 years2
... 
idn yearsn

Where:

• n is the total number of citizens.
• k is the number of permits to be issued.
• Each of the following n lines contains two integers: the citizen id and the number of years the citizen has lived in the town.

outputFormat

Output via stdout a single line containing the ids of the selected citizens (the first k entries after sorting by the given criteria) separated by a single space.

## sample

5 3
101 20
103 10
102 30
104 30
105 10

102 104 101