问题描述

给定一个长度为 $n$ 的序列 $a_1, a_2, · · · , a_n$，和一个正整数 $C$。求

$$\max_{S\subseteq \{1,2,\cdots,n\}}\left(\left(\sum_{1\le l\le r\le n}\prod_{i=l}^r[i\in S]\right)C-\sum_{i\in S}a_i\right)$$

这个问题太简单了，因此你需要支持 $m$ 次单点修改。

但这样就太难了，因此修改是临时修改，不会保留。

输入格式

输入的第一行包含三个整数 $n, m, C$。

输入的第二行包含 $n$ 个整数，表示序列 $a$。

接下来 $m$ 行，每行包含两个整数 $x, y$，表示询问将 $a_x$ 修改为 $y$ 之后的答案。

输出格式

输出 $m + 1$ 行，每行包含一个整数。

第一行表示所有修改开始之前，题中算式的值。

第 $i + 1$ 行表示如果执行第 $i$ 次修改，题中算式的值会变为多少。

输入样例1

5 2 1
1 1 4 1 1
3 2
3 10

输出样例1

7
9
2

输入样例2

12 10 2
2 3 2 7 8 3 2 1 20 5 15 20
9 3
11 1
5 35
6 15
12 1
1 9
4 3
10 2
5 1
7 6

输出样例2

68
85
82
41
56
87
61
72
71
75
64

数据范围

对于所有数据，保证 $1 ≤ n ≤ 3 × 10^5，0 ≤ m ≤ 3 × 10^5，1 ≤ C ≤ 10^5，1 ≤ x ≤ n，0 ≤ a_i , y ≤ 10^9$。

测试点	$n\leq$	$m\leq$	特殊性质
$1,2$	$15$		无
$3\sim 6$	$300$
$7\sim 10$	$2000$
$11,12$	$3\times 10^5$	$0$
$13,14$		$3\times 10^5$	$x\leq 10$
$15,16$	$10^5$		无
$17\sim 20$	$3\times 10^5$