题目描述

奥特曼有n颗宝石，每颗宝石的价值为vi，重量为wi。奥特曼重新建造自己的别墅， 不得已要卖掉部分宝石，它想留下k颗宝石，并要求(v1+v2+....vk)/(w1+w2+...wk)的值最大，请帮助它决定留下哪些宝石吧。

输入格式

第1行：两个以空格分隔的整数，n表示总的宝石的数量，k表示奥特曼想要留下的宝石的数量，1 ≤ k ≤ n ≤ 100000；
第2..N + 1行：第i + 1行包含两个整数，vi表示每颗宝石的价值，wi表示每颗宝石的重量，0 ≤ vi ≤ 10^6, 1 ≤ wi ≤ 10^6。

输出格式

一行k个数字，表示留下的宝石的编号（从小到大）。

样例数据

input

3  2
1   1
1   2
1   3

output

1   2