Demy has *n* jewels. Each of her jewels has some value *v _{i}* and weight

Since her husband John got broke after recent financial crises, Demy has decided to sell some jewels. She has decided that she would keep *k* best jewels for herself. She decided to keep such jewels that their specific value is as large as possible. That is, denote the specific value of some set of jewels *S* = {*i*_{1}, *i*_{2}, …, *i _{k}*} as

.

Demy would like to select such *k* jewels that their specific value is maximal possible. Help her to do so.

The first line of the input file contains *n* — the number of jewels Demy got, and *k* — the number of jewels she would like to keep (1 ≤ *k* ≤ *n* ≤ 100 000).

The following *n* lines contain two integer numbers each — *v _{i}* and

Output *k* numbers — the numbers of jewels Demy must keep. If there are several solutions, output any one.

3 2 1 1 1 2 1 3

1 2