#434. 【NFLSPC #2】雪

题目类型:传统型 时间限制:2000 ms 空间限制:512 MiB
输入文件:标准输入 输出文件:标准输出 答案检查器:文本比较

地上有$n$个数 第$i$个为$a_i$ 满足$-10^9 \leq a_i \leq 10^9$

下雪了 所有数都被雪覆盖了

你现在可以无限制地做如下操作 选择连续$k$个数 将被雪覆盖的数上的雪移去 将未被雪覆盖的数用雪覆盖

求未被雪覆盖的数的和的最大值为多少?

有$q$次修改操作 将$a_x$改为 $y$ 满足$1 \leq x \leq n$ 且 $-10^9 \leq y \leq 10^9$


输入格式

第一行 三个整数 $n$ $k$ $q$

下一行$n$个整数$a_i$

下$q$行每行两个整数 $x$ $y$

输出格式

$q+1$行 每行一个整数 表示最大值


样例一

input

2 2 2
1 1
1 -2
1 2

output

2
0
3

限制与约定

$1 \leq k \leq n \leq 100000$

$1 \leq q \leq 100000$

$-10^9 \leq a_i \leq 10^9$

$1 \leq x \leq n$ 且 $-10^9 \leq y \leq 10^9$

时间限制:$2\texttt{s}$

空间限制:$512\texttt{MB}$


$by\ \text{skyline}$