你有一份包含 $N$ 场即将到来的讲座的时间表，你可以选择参加。讲座按时间顺序编号为 $1$ 到 $N$。根据当前的时间表，你预计第 $i$ 场讲座的质量为 $a_i$。由于大多数讲座都很无聊，你只愿意参加某一组连续的 $K$ 场讲座。你将跳过其余的讲座，以便补觉并参加编程竞赛。由于你不喜欢记笔记，你只能记住你参加的讲座中其中 $2$ 场的内容。你希望选择参加的讲座以及记住的 $2$ 场讲座，以使这两场讲座的质量之和最大化。

时间表会有 $Q$ 次变更。第 $j$ 次变更由两个值 $i_j, x_j$ 表示，意味着第 $i_j$ 场讲座的质量变为 $x_j$。对于 $Q+1$ 个版本的日程表，请分别找出你能获得的最大讲座质量之和。

输入格式

第一行包含三个整数 $N, K$ 和 $Q$ ($2 \le N \le 10^6, 2 \le K \le N, 0 \le Q \le 10^5$)。 第二行包含 $N$ 个整数 $a_1, \dots, a_N$ ($0 \le a_i \le 10^9$)。接下来的 $Q$ 行，每行包含两个整数 $i_j$ 和 $x_j$ ($1 \le i_j \le N, 0 \le x_j \le 10^9$)。

在总分 $25$ 分中，有 $5$ 分满足 $Q = 0$。 另有 $10$ 分满足 $N \le 10^4$。

输出格式

输出 $Q+1$ 行，每行包含一个整数。第 $j$ 行应包含在进行了前 $j-1$ 次变更后，当前日程表所能达到的最大值。

样例

输入 1

4 3 1
6 1 2 4
1 3

输出 1

8
6

说明 1

对于原始日程表，最好参加前三场讲座并记住第一场和第三场，总价值为 $6 + 2 = 8$。更新后，最好参加最后三场讲座并记住最后两场，总价值为 $2 + 4 = 6$。