CF730D.Running Over The Bridges

Polycarp is playing a game called "Running Over The Bridges". In this game he has to run over n bridges from the left to the right. Bridges are arranged one after the other, so the i-th bridge begins where the (i - 1)-th bridge ends.

You have the following data about bridges: l__i and t__i — the length of the i-th bridge and the maximum allowed time which Polycarp can spend running over the i-th bridge. Thus, if Polycarp is in the beginning of the bridge i at the time T then he has to leave it at the time T + t__i or earlier. It is allowed to reach the right end of a bridge exactly at the time T + t__i.

Polycarp can run from the left side to the right one with speed 0.5, so he will run over a bridge with length s in time 2·s. Besides, he has several magical drinks. If he uses one drink, his speed increases twice (i.e. to value 1) for r seconds. All magical drinks are identical. Please note that Polycarp can use a drink only at integer moments of time, and he drinks it instantly and completely. Additionally, if Polycarp uses a drink at the moment T he can use the next drink not earlier than at the moment T + r.

What is the minimal number of drinks Polycarp has to use to run over all n bridges? If this number is not greater than 105, then you have to find out the moments of time when Polycarp has to use each magical drink.

波利卡普正在玩一款名为“跨越桥梁”的游戏。在该游戏中，他需要从左到右依次跑过 $n$ 座桥梁。这些桥梁首尾相接，即第 $i$ 座桥梁的起点恰好是第 $i-1$ 座桥梁的终点。

你已知每座桥梁的信息：$l_i$ 和 $t_i$ —— 分别表示第 $i$ 座桥梁的长度以及波利卡普跑过该桥所允许的最大耗时。也就是说，若波利卡普在时刻 $T$ 到达第 $i$ 座桥梁的左端点，则他必须在时刻 $T + t_i$ 或更早到达其右端点。在时刻 $T + t_i$ 恰好抵达右端点是被允许的。

波利卡普的基础奔跑速度为 $0.5$，因此他跑过一座长度为 $s$ 的桥梁所需时间为 $2 \cdot s$。此外，他拥有若干瓶魔法药水。每使用一瓶药水，他的速度将在接下来的 $r$ 秒内提升至原来的两倍（即变为 $1$）。所有魔法药水完全相同。注意：波利卡普只能在整数时刻使用药水，且饮用过程瞬间完成；此外，若他在时刻 $T$ 使用了一瓶药水，则下一瓶药水最早可在时刻 $T + r$ 使用。

问：波利卡普至少需要使用多少瓶魔法药水才能成功跑完全部 $n$ 座桥梁？若该最小瓶数不超过 $10^5$，则还需输出每瓶药水应使用的具体时刻。

The first line contains two integers n and r (1 ≤ n ≤ 2·105, 1 ≤ r ≤ 1012) — the number of bridges and the duration of the effect of a magical drink.

The second line contains a sequence of integers _l_1, _l_2, ..., l__n (1 ≤ l__i ≤ 5·106), where l__i is equal to the length of the i-th bridge.

The third line contains a sequence of integers _t_1, _t_2, ..., t__n (1 ≤ t__i ≤ 107), where t__i is equal to the maximum allowed time which Polycarp can spend running over the i-th bridge.

第一行包含两个整数 $n$ 和 $r$（$1 ≤ n ≤ 2·10^5$，$1 ≤ r ≤ 10^{12}$）—— 分别表示桥的数量以及魔法药水效果的持续时间。

第二行包含一个整数序列 $l_1, l_2, ..., l_n$（$1 ≤ l_i ≤ 5·10^6$），其中 $l_i$ 表示第 $i$ 座桥的长度。

第三行包含一个整数序列 $t_1, t_2, ..., t_n$（$1 ≤ t_i ≤ 10^7$），其中 $t_i$ 表示 Polycarp 在第 $i$ 座桥上奔跑所允许花费的最大时间。

The first line of the output should contain k — the minimal number of drinks which Polycarp has to use, or -1 if there is no solution.

If the solution exists and the value of k is not greater than 105 then output k integers on the next line — moments of time from beginning of the game when Polycarp has to use drinks. Print the moments of time in chronological order. If there are several solutions, you can output any of them.

输出的第一行应包含 k — Polycarp 需要使用的饮料的最少数量；若无解，则输出 -1。

如果解存在且 k 的值不超过 $10^5$，则在下一行输出 k 个整数 —— Polycarp 需要使用饮料的时刻（从游戏开始起计）。请按时间顺序输出这些时刻。若存在多个解，可输出其中任意一个。

In the first case, there is only one bridge and it is clear that Polycarp cannot run over it without magical drinks. So, if he will use one magical drink on start (moment of time 0), and the second one — three seconds later (moment of time 3), he will be able to reach the end of the bridge in time. Please note, in this case there are several possible answers to the problem. For example, Polycarp can use the first drink at the moment of time 4 and the second one — at the moment of time 7.

In the second case, Polycarp cannot run over all bridges even if he will use magical drinks. So, answer in this case is -1.

In the fourth case, Polycarp can run over all bridges without magical drinks.

在第一种情况下，只有一座桥，显然波利卡普不喝魔法药水就无法跑过这座桥。因此，如果他在起始时刻（时间 0）使用第一瓶魔法药水，再在三秒后（时间 3）使用第二瓶，他便能及时抵达桥的终点。请注意，在本例中，该问题存在多种可能的解。例如，波利卡普也可以在时间 4 使用第一瓶药水，在时间 7 使用第二瓶。

在第二种情况下，即使波利卡普使用魔法药水，他也无法跑过所有桥。因此，本例的答案为 $-1$。

在第四种情况下，波利卡普无需使用魔法药水即可跑过所有桥。