梦迹
题号：NC248249
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

云浅现在手上没有数了，不过她变出来了 n 个非负整数 。她又给了你一个非负整数 W。
现在有 q 次修改，每次给出 p,x，你需要令 。
在每次修改后，你需要输出满足 的数对 (i,j) 的个数。

输入描述:

第一行三个正整数 n,q,W。
第二行 n 个正整数  表示云浅的 n 个数。
接下来 q 行，每行两个非负整数 p,x，表示一次修改。
对于  的数据，。

输出描述:

输出 q 行，表示每次修改后满足  的数对 (i,j) 的个数。

示例1

输入

复制 
4 3 6
1 0 4 6 
2 2
4 4
1 2

输出

复制 
5
7
7

说明

第一次操作后，a=(1,2,4,6)，符合条件的 (i,j) 有：(1,1),(1,2),(1,3),(2,2),(2,3)。
第二次操作后，a=(1,2,4,4)，符合条件的 (i,j) 有：(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4)。
第三次操作后，a=(2,2,4,4)，符合条件的 (i,j) 有：(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4)。

备注:

对于  的数据，。