G - Car Safety Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

左右に伸びる数直線上を N 台の車が走っています。座標は右向きが正の向きに定められています。

i 番目の車は、座標 A_i に現在いて、正方向へ B_i の速度で動いています。ここで、車の座標は全て相異なります。

i 番目の車は以下の条件を満たすとき、安全であるといいます。

  • i 番目の車より右にいるどの車とも座標が B_i\times K 以上離れている。

安全でない車の番号を全て昇順に出力してください。

制約

  • 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

出力

2 行出力せよ。1 行目には安全でない車の個数を出力せよ。

2 行目には安全でない車の番号全てを昇順に空白区切りで出力せよ。

入力例 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 未満です。よって安全ではありません。

4 番目の車も同様に安全ではありません。

車の番号を昇順に出力することに注意してください。

入力例 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

Problem Statement

There are N cars on a number line extending left and right. The positive coordinate direction points to the right.

The i-th car, whose ID is i, is currently at coordinate A_i and moving at a speed of B_i in the positive direction. The coordinates of the cars are pairwise distinct.

Car i is considered safe if and only if:

  • every car to the right of car i is distant by at least B_i\times K from car i.

Print the IDs of the cars that are not safe in ascending order.

Constraints

  • 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)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N K
A_1 B_1
\vdots
A_N B_N

Output

Print two lines. The first line should contain the number of cars that are not safe.

The second line should contain the IDs of the cars that are not safe in ascending order, separated by spaces.

Sample Input 1

4 2
1 1
10 5
3 3
7 2

Sample Output 1

2
3 4

Car 1 is distant by at least 1\times 2=2 from every car to its right, so it is safe.

Meanwhile, car 3 is distant from car 4 to its right by 7-3=4, which is less than 3\times 2=6, so car 3 is not safe.

Likewise, car 4 is not safe either.

Note that car IDs should be printed in ascending order.

Sample Input 2

10 2
25 9
22 10
7 5
5 7
27 10
6 7
21 6
2 1
9 3
24 10

Sample Output 2

7
1 2 3 4 6 7 10