如您所知,旅鼠喜欢跳跃。在下一个壮观的集体跳跃中,旅鼠聚集在一块高高的岩石附近,上面有 k 个舒适的壁架。第一个壁架位于 h 米的高度,第二个壁架位于 2h 米的高度,依此类推(第 i 个壁架位于 i·h 米的高度)。日落时旅鼠就要跳跃了,剩下的时间不多了。
每只旅鼠的特征是每分钟 vi 米的攀爬速度和 mi 的重量。这意味着第 i 个旅鼠可以在 $$\frac{j \cdot h}{v_i}$$ 分钟内爬到第 j 个壁架。
为了使跳跃更漂亮,较重的旅鼠应该从较高的壁架上跳下:如果一只重量为 mi 的旅鼠从壁架 i 跳起,而一只重量为 mj 的旅鼠从壁架 j 跳起(对于 i < j),则应满足不等式 mi ≤ mj。
由于有 n 只旅鼠且只有 k 个壁架 (k ≤ n),因此需要选择将参与跳跃的 k 只旅鼠。选定的旅鼠应按 1 到 k 的顺序分布在壁架上,每个壁架一只旅鼠。旅鼠应按照重量不随壁架高度增加而减少的顺序排列。另外,每只旅鼠应该有足够的时间到达他的壁架,也就是说,他的攀登时间不应超过t分钟。旅鼠同时爬上壁架,互不干扰。
找到安排旅鼠跳跃的方法,使时间 t 最小化。
输入
第一行包含空格分隔的整数 n、k 和 h (1 ≤ k ≤ n ≤ 105, 1 ≤ h ≤ 104) — 旅鼠总数、壁架数量以及相邻壁架之间的距离。
第二行包含 n 个空格分隔的整数 m1, m2, ..., mn (1 ≤ mi ≤ 109),其中 mi 是第 i 个旅鼠的权重。
第三行包含 n 个空格分隔的整数 v1, v2, ..., vn (1 ≤ vi ≤ 109),其中 vi 是第 i 个旅鼠的速度。
输出
打印从 1 到 n 的 k 个不同数字 — 如果以最佳方式组织跳跃,则相应地前往高度为 h、2h、...、kh 的旅鼠的数量。如果有多种选择旅鼠的方法,请选择其中一种。
示例
输入 #1
5 3 2 1 2 3 2 1 1 2 1 2 10
输出 #1
5 2 4
输入 #2
5 3 10 3 4 3 2 1 5 4 3 2 1
输出 #2
4 3 1
注意
让我们考虑第一个示例案例。第五只旅鼠(速度 10)在 $$\frac{1}{5}$$ 分钟内到达高度 2 的壁架;第二只旅鼠(速度 2)在 2 分钟内到达高度 4 的壁架;第四只旅鼠(速度 2)在 3 分钟内到达高度 6 的壁架。所有旅鼠都设法在 3 分钟内占据自己的位置。