题目描述

问题 F 和 F2 具有相同的问题描述，但约束条件和时间限制不同。

高桥的酒窖里有 $N$ 瓶酒，从左到右排列着。
第 $i$ 瓶酒的美味程度为 $A_i$。
青木要从这些 $N$ 瓶酒中选择 $K$ 瓶并偷走它们。然而，如果满足以下条件，高桥足够仔细，会注意到这次偷窃行为：

• 存在 $D$ 个连续的瓶子，其中至少两个被偷走。（在本问题中，$D = 2$。）

对于每种不被高桥注意到的偷窃方式，找到被偷走的瓶子的总美味度，然后求出所有这些值的和。
由于和可能非常大，输出结果需要对 $998244353$ 取模。

约束条件

• $D = 2$
• $2 \le N \le 3 \times 10^5$
• $1 \le K \le \left\lceil \frac{N}{D} \right\rceil$（$\left\lceil x \right\rceil$ 表示不小于 $x$ 的最小整数。）
• $1 \le A_i < 998244353$
• 输入中的所有值都是整数。

输入

从标准输入读入数据，格式如下：

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

输出

以 $998244353$ 为模输出答案。

示例输入 1

4 2 2
1 4 2 3

示例输出 1

14

可行的偷窃方式和每种方式的总美味度如下：

• 从左边偷走第 $1$、$3$ 瓶酒，总美味度为 $1 + 2 = 3$。
• 从左边偷走第 $1$、$4$ 瓶酒，总美味度为 $1 + 3 = 4$。
• 从左边偷走第 $2$、$4$ 瓶酒，总美味度为 $4 + 3 = 7$。

因此，答案为 $3 + 4 + 7 = 14$。

示例输入 2

5 3 2
4 7 5 3 8

示例输出 2

17

只能偷走第 $1$、$3$、$5$ 瓶酒。

示例输入 3

12 4 2
107367523 266126484 149762920 57456082 857431610 400422663 768881284 494753774 152155823 740238343 871191740 450057094

示例输出 3

136993014