B - マラソン大会 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 233 点

問題文

高橋君と青木君は、マラソン大会に参加しています。このマラソンコースには N 個のチェックポイントがあり、選手はこれらを 1 番目から N 番目まで順番に通過していきます。

i 番目のチェックポイントから i + 1 番目のチェックポイントまでの距離は D_i メートルです（1 \leq i \leq N-1）。

レース開始時点（時刻 0 秒）で、両者は同時に 1 番目のチェックポイントをスタートしました。

高橋君は休憩をとらず一定のペースで走り続け、1 秒あたり V メートルの速さで進みます。したがって、高橋君が i 番目のチェックポイント（2 \leq i \leq N）に到着する時刻は \displaystyle\frac{D_1 + D_2 + \cdots + D_{i-1}}{V} 秒です。この値は整数とは限りません。

一方、青木君はペースにムラがあり、i 番目のチェックポイントに時刻 T_i 秒ちょうどに到着することがわかっています。ここで T_1 = 0 です。青木君の到着時刻は T_1 < T_2 < T_3 < \cdots < T_N を満たします。

2 番目以降の各チェックポイント i（2 \leq i \leq N）について、高橋君の到着時刻が青木君の到着時刻 T_i より真に小さいとき、すなわち

D_1 + D_2 + \cdots + D_{i-1} < T_i \times V

が成り立つとき、高橋君はチェックポイント i で青木君に先着したといいます。同時に到着した場合は先着には含みません。

高橋君が青木君に先着するチェックポイントの番号をすべて求め、小さい順に出力してください。先着するチェックポイントが一つもない場合は -1 を出力してください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq V \leq 10^9
  • 1 \leq D_i \leq 10^9 (1 \leq i \leq N-1)
  • T_1 = 0
  • 1 \leq T_i \leq 10^{18} (2 \leq i \leq N)
  • T_i < T_{i+1} (1 \leq i \leq N-1)
  • 入力はすべて整数

入力

N V
D_1 D_2 \cdots D_{N-1}
T_2 T_3 \cdots T_N
  • 1 行目には、チェックポイントの数 N と、高橋君の速さ V（メートル毎秒）が、スペース区切りで与えられる。
  • 2 行目には、i 番目のチェックポイントから i + 1 番目のチェックポイントまでの距離 D_i（メートル）が N - 1 個（i = 1, 2, \ldots, N-1 の順）、スペース区切りで与えられる。
  • 3 行目には、青木君が i 番目のチェックポイントに到着する時刻 T_i（秒）が N - 1 個（i = 2, 3, \ldots, N の順）、スペース区切りで与えられる。T_1 = 0 は入力には含まれない。

出力

高橋君が青木君に先着するチェックポイントの番号を、小さい順にスペース区切りで 1 行に出力してください。先着するチェックポイントが一つもない場合は -1 を出力してください。

入力例 1

5 10
30 50 40 60
4 10 15 20

出力例 1

2 3 4 5

入力例 2

4 5
100 100 100
10 20 30

出力例 2

-1

入力例 3

8 100
500 300 700 200 400 600 800
4 8 20 25 35 50 80

出力例 3

4 5 6 7 8

Score : 233 pts

Problem Statement

Takahashi and Aoki are participating in a marathon race. The marathon course has N checkpoints, and runners pass through them in order from the 1-st to the N-th.

The distance from the i-th checkpoint to the (i + 1)-th checkpoint is D_i meters (1 \leq i \leq N-1).

At the start of the race (time 0 seconds), both of them started simultaneously from the 1-st checkpoint.

Takahashi runs at a constant pace without taking any breaks, advancing at a speed of V meters per second. Therefore, the time at which Takahashi arrives at the i-th checkpoint (2 \leq i \leq N) is \displaystyle\frac{D_1 + D_2 + \cdots + D_{i-1}}{V} seconds. This value is not necessarily an integer.

On the other hand, Aoki runs at an uneven pace, and it is known that he arrives at the i-th checkpoint at exactly time T_i seconds. Here, T_1 = 0. Aoki's arrival times satisfy T_1 < T_2 < T_3 < \cdots < T_N.

For each checkpoint i from the 2-nd onward (2 \leq i \leq N), if Takahashi's arrival time is strictly less than Aoki's arrival time T_i, that is, if

D_1 + D_2 + \cdots + D_{i-1} < T_i \times V

holds, then Takahashi is said to have arrived first at checkpoint i ahead of Aoki. If they arrive at the same time, it does not count as arriving first.

Find all checkpoint numbers where Takahashi arrives first ahead of Aoki, and output them in ascending order. If there are no such checkpoints, output -1.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq V \leq 10^9
  • 1 \leq D_i \leq 10^9 (1 \leq i \leq N-1)
  • T_1 = 0
  • 1 \leq T_i \leq 10^{18} (2 \leq i \leq N)
  • T_i < T_{i+1} (1 \leq i \leq N-1)
  • All input values are integers.

Input

N V
D_1 D_2 \cdots D_{N-1}
T_2 T_3 \cdots T_N
  • The first line contains the number of checkpoints N and Takahashi's speed V (meters per second), separated by a space.
  • The second line contains N - 1 distances D_i (meters) from the i-th checkpoint to the (i + 1)-th checkpoint (in order of i = 1, 2, \ldots, N-1), separated by spaces.
  • The third line contains N - 1 arrival times T_i (seconds) at which Aoki arrives at the i-th checkpoint (in order of i = 2, 3, \ldots, N), separated by spaces. T_1 = 0 is not included in the input.

Output

Output the checkpoint numbers where Takahashi arrives first ahead of Aoki, in ascending order, separated by spaces, on a single line. If there are no such checkpoints, output -1.

Sample Input 1

5 10
30 50 40 60
4 10 15 20

Sample Output 1

2 3 4 5

Sample Input 2

4 5
100 100 100
10 20 30

Sample Output 2

-1

Sample Input 3

8 100
500 300 700 200 400 600 800
4 8 20 25 35 50 80

Sample Output 3

4 5 6 7 8