O - Decode

問題文

正整数 $N,M,K$ および長さ $N$ の正整数列 $A=(A_1,A_2,…,A_N)$ が与えられます．
ここで，「 $1$ 以上 $N$ 以下の整数 $i$ について，$A_i$ を $A_1$ から $A_i$ までの $i$ 個の数の総和に更新することを同時に行う」という操作を Imos操作 と名付けます．
$K$ 回Imos操作を行うことで数列 $A$ と一致するような数列を $P=(P_1,P_2,…,P_N)$ としたとき，$P_M-x$が $998244353$ の倍数となるような $0$ 以上 $998244353$ 未満の整数 $x$ を求めてください．
ただし，条件を満たす数列 $P$ は $1$ つしか存在しないことが保証されます．

制約

• 入力はすべて整数
• $1 \leq N \leq 2 \cdot 10^5$
• $1 \leq M \leq N$
• $1 \leq K \leq 2 \cdot 10^5$
• $1 \leq A_i \leq 2 \cdot 10^5$

小課題

1. (40点) $K=1$
2. (60点) 追加の制約はない

入力

入力は以下の形式で標準入力から与えられる．

$N~M~K$

$A_1~A_2~...~A_N$

出力

求めるべき数列を $P=(P_1,P_2,…,P_N)$ としたとき，$P_M-x$ が $998244353$ の倍数となるような $0$ 以上 $998244353$ 未満の整数 $x$ を出力せよ．

入力例1

5 3 1
3 1 4 1 5
Copy

出力例1

3
Copy

数列 $P$ を $(3,-2,3,-3,4)$ とすると，Imos操作を $1$ 回行ったときに $(3,1,4,1,5)$ となることが分かるので，出力するべきは $3$ です．
この入力例はすべての小課題の制約を満たします．

入力例2

8 7 5
2 7 1 8 2 8 1 8
Copy

出力例2

998244252
Copy

数列 $P$ を $(2,-3,-14,53,-88,101,-101,102)$ とすると，Imos操作を $5$ 回行ったときに $(2,7,1,8,2,8,1,8)$ となることが分かるので，出力するべきは $998244252$ です．
この入力例は小課題2の制約を満たします．