AT_arc120_f2.[ARC120F2] Wine Thief

问题 F 和问题 F2 是相同的问题，但约束条件和运行时间限制不同。

高桥君的仓库里有 $N$ 瓶葡萄酒，按左右方向排成一列。从左边数第 $i$ 瓶葡萄酒的美味度为 $A_i$。
青木君现在要从这 $N$ 瓶葡萄酒中，恰好选出 $K$ 瓶进行偷窃。但是，高桥君非常警觉，如果满足以下条件，他就会发现被偷了：

• 存在连续排列的 $D$ 瓶葡萄酒，其中被偷走的有 $2$ 瓶或以上。

请你求出所有不会被高桥君发现的偷窃方案中，偷走的葡萄酒美味度之和的总和。
由于答案可能非常大，请输出其对 $998244353$ 取模的结果。

输入以如下格式从标准输入给出：

$N$ $K$ $D$ $A_1$ $A_2$ $A_3$ $\dots$ $A_N$

输出答案对 $998244353$ 取模的结果。

约束条件

• $2 \leq D \leq N \leq 10^6$
• $1 \leq K \leq \left\lceil \frac{N}{D} \right\rceil$（$\left\lceil x \right\rceil$ 表示不小于 $x$ 的最小整数）
• $1 \leq A_i < 998244353$
• 输入中的所有值均为整数

样例解释 1

偷窃方案及其美味度之和如下：

• 偷第 $1$ 瓶和第 $3$ 瓶：美味度之和为 $1 + 2 = 3$
• 偷第 $1$ 瓶和第 $4$ 瓶：美味度之和为 $1 + 3 = 4$
• 偷第 $2$ 瓶和第 $4$ 瓶：美味度之和为 $4 + 3 = 7$
  因此答案为 $3 + 4 + 7 = 14$。

样例解释 2

偷窃方案及其美味度之和如下：

• 偷第 $1$ 瓶和第 $4$ 瓶：美味度之和为 $1 + 7 = 8$
• 偷第 $1$ 瓶和第 $5$ 瓶：美味度之和为 $1 + 3 = 4$
• 偷第 $2$ 瓶和第 $5$ 瓶：美味度之和为 $5 + 3 = 8$

由 ChatGPT 4.1 翻译