问题陈述
有 N 左右延伸的数轴上的汽车。 正坐标方向指向右侧。
的 i第辆车,其 ID 为 i,当前位于坐标 A_i 并以以下速度移动 B_i 正方向。 汽车的坐标是两两不同的。
汽车 当且仅当满足以下条件时, i 才被认为是安全的:
- 该车右侧的每辆车 i 至少相距 B_i\times K 来自汽车 i.
打印正在运行的汽车的 ID 不 安全 升序 订单。
约束
- 2\leq N\leq 2\times 10^5
- 1\leq K\leq 10^9
- 1\leq A_i,B_i\leq 10^9
- A_i\neq A_j\ (i\neq j)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N K A_1 B_1 \vdots A_N B_N
输出
打印两行。 第一行应包含不安全的汽车数量。
第二行应包含按升序排列的不安全汽车的 ID,并用空格分隔。
示例输入 1
4 2 1 1 10 5 3 3 7 2
示例输出 1
2 3 4
汽车 当且仅当满足以下条件时, 1 至少相距 1\times 2=2 每辆车都在其右侧,所以很安全。
同时,汽车 3 离车较远 4 在其右侧 7-3=4,小于 3\times 2=6,所以车 3 不安全。
同样,汽车 4 也不安全。
请注意,汽车 ID 应按升序打印。
示例输入 2
10 2 25 9 22 10 7 5 5 7 27 10 6 7 21 6 2 1 9 3 24 10
示例输出 2
7 1 2 3 4 6 7 10