一位旅行者正在计划沿河进行水上徒步旅行。他记下了当晚合适的休息点,并写下了距起点的距离。这些位置中的每一个都进一步以其风景如画为特征,因此对于第 i 个休息点,距起点的距离等于 xi,其风景如画等于 bi。旅行者将沿着河流朝一个方向移动,我们可以假设他将从坐标轴上的0点开始,其余点是坐标为xi的点。
旅行者每天都想走 l 的距离。实际上,事实证明这并不总是可能的,因为他需要在其中一个休息点结束每一天。此外,旅行者还可以在两个愿望之间进行选择:每天行驶距离 l 和参观最风景如画的地方。
让我们假设,如果旅行者一天内走了距离 rj,那么他会感到沮丧 $$\sqrt{|r_{j}-l|}$$,并且他对徒步旅行的总沮丧被计算为所有天的总沮丧。
帮助他规划路线,以尽量减少相对总的挫败感:总的挫败感除以他所使用的所有休息点的总风景如画。
旅行者的路径必须终止于最远的休息点。
输入
输入的第一行包含整数 n, l (1 ≤ n ≤ 1000, 1 ≤ l ≤ 105) — 休息点的数量和一天路径的最佳长度。
接下来是 n 行,每行将一个休息点描述为一对整数 xi, bi (1 ≤ xi, bi ≤ 106)。没有两个休息点具有相同的 xi,线按照 xi 严格递增的顺序给出。
输出
将旅行者的路径打印为他使用的休息点编号的序列(按照他使用这些休息点的顺序)。按照 xi 递增的顺序对点从 1 到 n 进行编号。最后打印的数字必须等于n。
示例
输入 #1
5 9 10 10 20 10 30 1 31 5 40 10
输出 #1
1 2 4 5
注意
在样本测试中,相对总挫败感的最小值大约等于 0.097549。该值的计算公式为 $$(1+1+\sqrt{2}+0)/(10+10+5+10)$$。