#434. 【NFLSPC #2】雪

Type : Normal Time Limit : 2000 ms Memory Limit : 512 MiB
Input File : Standard Input Output File : Standard Outout Checker : Text Comparison

地上有$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}$