English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
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.
[samples]
## Note
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.
Polycarp 正在玩一个名为 "Running Over The Bridges" 的游戏。在这个游戏中，他必须从左到右跑过 #cf_span[n] 座桥。这些桥依次排列，因此第 #cf_span[i] 座桥的起点位于第 #cf_span[(i - 1)] 座桥的终点处。
你拥有以下关于桥的数据：#cf_span[li] 和 #cf_span[ti] —— 分别表示第 #cf_span[i] 座桥的长度和 Polycarp 跑过该桥允许花费的最大时间。因此，如果 Polycarp 在时间 #cf_span[T] 到达第 #cf_span[i] 座桥的起点，则他必须在时间 #cf_span[T + ti] 或更早离开该桥。允许他在时间 #cf_span[T + ti] 恰好到达桥的右端。
Polycarp 以速度 #cf_span[0.5] 从左向右奔跑，因此他跑过长度为 #cf_span[s] 的桥需要时间 #cf_span[2·s]。此外，他拥有若干魔法饮料。如果他使用一瓶饮料，他的速度会翻倍（即变为 1），持续 #cf_span[r] 秒。所有魔法饮料完全相同。请注意，Polycarp 只能在 *整数* 时刻使用饮料，并且他立即完全饮用。此外，如果 Polycarp 在时刻 #cf_span[T] 使用一瓶饮料，则他至少要在时刻 #cf_span[T + r] 才能使用下一瓶。
请问 Polycarp 跑过所有 #cf_span[n] 座桥所需的最少饮料数量是多少？如果这个数量不超过 #cf_span[105]，你还需要找出 Polycarp 使用每瓶魔法饮料的具体时刻。
第一行包含两个整数 #cf_span[n] 和 #cf_span[r]（#cf_span[1 ≤ n ≤ 2·105]，#cf_span[1 ≤ r ≤ 1012]）——桥的数量和魔法饮料效果的持续时间。
第二行包含一个整数序列 #cf_span[l1, l2, ..., ln]（#cf_span[1 ≤ li ≤ 5·106]），其中 #cf_span[li] 表示第 #cf_span[i] 座桥的长度。
第三行包含一个整数序列 #cf_span[t1, t2, ..., tn]（#cf_span[1 ≤ ti ≤ 107]），其中 #cf_span[ti] 表示 Polycarp 跑过第 #cf_span[i] 座桥允许花费的最大时间。
输出的第一行应包含 #cf_span[k] —— Polycarp 所需使用的最少饮料数量，若无解则输出 _-1_。
如果存在解且 #cf_span[k] 不超过 #cf_span[105]，则在下一行输出 #cf_span[k] 个整数，表示 Polycarp 使用饮料的时刻（从游戏开始计时）。按时间顺序输出。若有多种解，输出任意一种即可。
在第一个例子中，只有一座桥，显然 Polycarp 不使用魔法饮料无法跑过它。因此，如果他在起点（时刻 #cf_span[0]）使用一瓶饮料，再在三秒后（时刻 #cf_span[3]）使用第二瓶，他就能在时限内到达桥的终点。请注意，本题存在多种可能答案。例如，Polycarp 可以在时刻 #cf_span[4] 使用第一瓶饮料，在时刻 #cf_span[7] 使用第二瓶。
在第二个例子中，即使 Polycarp 使用魔法饮料，也无法跑过所有桥。因此本例答案为 _-1_。
在第四个例子中，Polycarp 无需使用魔法饮料即可跑过所有桥。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[r]（#cf_span[1 ≤ n ≤ 2·105]，#cf_span[1 ≤ r ≤ 1012]）——桥的数量和魔法饮料效果的持续时间。第二行包含一个整数序列 #cf_span[l1, l2, ..., ln]（#cf_span[1 ≤ li ≤ 5·106]），其中 #cf_span[li] 表示第 #cf_span[i] 座桥的长度。第三行包含一个整数序列 #cf_span[t1, t2, ..., tn]（#cf_span[1 ≤ ti ≤ 107]），其中 #cf_span[ti] 表示 Polycarp 跑过第 #cf_span[i] 座桥允许花费的最大时间。
## Output
输出的第一行应包含 #cf_span[k] —— Polycarp 所需使用的最少饮料数量，若无解则输出 _-1_。如果存在解且 #cf_span[k] 不超过 #cf_span[105]，则在下一行输出 #cf_span[k] 个整数，表示 Polycarp 使用饮料的时刻（从游戏开始计时）。按时间顺序输出。若有多种解，输出任意一种即可。
[samples]
## Note
在第一个例子中，只有一座桥，显然 Polycarp 不使用魔法饮料无法跑过它。因此，如果他在起点（时刻 #cf_span[0]）使用一瓶饮料，再在三秒后（时刻 #cf_span[3]）使用第二瓶，他就能在时限内到达桥的终点。请注意，本题存在多种可能答案。例如，Polycarp 可以在时刻 #cf_span[4] 使用第一瓶饮料，在时刻 #cf_span[7] 使用第二瓶。在第二个例子中，即使 Polycarp 使用魔法饮料，也无法跑过所有桥。因此本例答案为 _-1_。在第四个例子中，Polycarp 无需使用魔法饮料即可跑过所有桥。
**Definitions**
Let $ n, r \in \mathbb{Z}^+ $ be the number of bridges and the duration of a magical drink’s effect.
Let $ L = (l_1, l_2, \dots, l_n) \in \mathbb{Z}^n $ be the sequence of bridge lengths.
Let $ T = (t_1, t_2, \dots, t_n) \in \mathbb{Z}^n $ be the sequence of maximum allowed times per bridge.
Let $ v_0 = 0.5 $ be the base speed, and $ v_1 = 1 $ be the enhanced speed (after using a drink).
Define the cumulative position after bridge $ i $:
$ p_0 = 0 $, and $ p_i = \sum_{j=1}^{i} l_j $ for $ i \in \{1, \dots, n\} $.
Let $ \tau_i $ be the earliest time Polycarp can reach the start of bridge $ i $ (i.e., position $ p_{i-1} $).
Let $ \tau_0 = 0 $.
Let $ d \in \{0,1\}^* $ be a binary sequence indicating when drinks are used: $ d_k = 1 $ if a drink is used at time $ x_k $, else $ d_k = 0 $.
Let $ X = \{x_1, x_2, \dots, x_k\} \subset \mathbb{Z}_{\geq 0} $ be the set of drink activation times, with $ x_{i+1} \geq x_i + r $.
At any time $ t $, Polycarp’s speed is:
$$
v(t) =
\begin{cases}
1 & \text{if } \exists\, x \in X \text{ such that } x \leq t < x + r \\
0.5 & \text{otherwise}
\end{cases}
$$
**Constraints**
1. $ 1 \leq n \leq 2 \cdot 10^5 $
2. $ 1 \leq r \leq 10^{12} $
3. $ 1 \leq l_i \leq 5 \cdot 10^6 $
4. $ 1 \leq t_i \leq 10^7 $
5. For each bridge $ i \in \{1, \dots, n\} $:
$$
\tau_i + \int_{\tau_i}^{\tau_i + t_i} v(s)\, ds \geq p_i
$$
(i.e., Polycarp must traverse bridge $ i $ within time window $ [\tau_i, \tau_i + t_i] $)
6. Drink usage times must satisfy $ x_{j+1} \geq x_j + r $ for all $ j $.
7. Drink usage times must be integers.
**Objective**
Find the minimal $ k = |X| $ such that the traversal constraint is satisfied for all bridges.
If no such $ k $ exists, output $ -1 $.
If $ k \leq 10^5 $, output the set $ X $ in increasing order.
API Response (JSON)
{
"problem": {
"name": "D. Running Over The Bridges",
"description": {
"content": "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 be",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF730D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 be...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Polycarp 正在玩一个名为 \"Running Over The Bridges\" 的游戏。在这个游戏中，他必须从左到右跑过 #cf_span[n] 座桥。这些桥依次排列，因此第 #cf_span[i] 座桥的起点位于第 #cf_span[(i - 1)] 座桥的终点处。\n\n你拥有以下关于桥的数据：#cf_span[li] 和 #cf_span[ti] —— 分别表示第 #cf_span[i]...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, r \\in \\mathbb{Z}^+ $ be the number of bridges and the duration of a magical drink’s effect. \nLet $ L = (l_1, l_2, \\dots, l_n) \\in \\mathbb{Z}^n $ be the sequence of bridge l...",
"is_translate": false,
"language": "Formal"
}
]
}