+ Time Limit: 1 second
+ Memory Limit: 256 megabytes
----------
We have an array consisting of $n$ numbers. A range of these numbers is called **beautiful** if and only if the sum of the numbers in this range is less than or equal to $k$ and greater than or equal to $-k$. In other words, the absolute value of the sum of the numbers in this range must be at most $k$.
On this array, $q$ operations have been performed. Each operation is defined as follows: two numbers $i$ and $x$ are specified ($1 \le i \le n-1$), and the $i$-th element of the array is incremented by $x$, and the $i+1$-th element of the array is decremented by $x$. (Note that the value of $x$ can be negative as well.)
You are asked to calculate the number of beautiful ranges in the array once at the beginning and then after each operation.
Please note that all operations are persistent, meaning their effects remain on the array for subsequent operations.
# Input
In the first line of input, three integers $n$, $k$, and $q$ are given in order.
In the second line, $n$ numbers are given, which are the initial values of the array, denoted as $a_i$.
$$ 2 \le n \le 100,000 $$
$$ 1 \le q \le 100,000 $$
$$ 0 \le k \le 10^9$$
$$ -10^9 \le a_i, x \le 10^9$$
$$ 1 \le i \le n - 1 $$
It is also guaranteed that the **absolute value** of all array elements after each query will be at most $10^9$.
# Output
Your output should consist of $q+1$ lines, showing the number of beautiful ranges in the array before and after each operation.
# Example
## Sample Input 1
```
5 3 2
1 2 3 4 5
3 -2
2 4
```
## Sample Output 1
```
4
5
4
```
In this example, initially, the beautiful ranges are $[1]$, $[2]$, $[3]$, and $[1,2]$.
After the first operation, the array becomes: $1, 2, 1, 6, 5$. Now, the beautiful ranges are $[1]$, $[2]$, $[3]$, $[1,2]$, and $[2,3]$.
After the second operation, the array becomes: $1, 6, -3, 6, 5$. Now, the beautiful ranges are $[1]$, $[3]$, $[2,3]$, and $[3,4]$.
(Meaning of the range $[i,j]$ is a range that starts from element $i$ and continues to element $j$)
## Sample Input 2
```
5 5 5
-3 -4 0 5 -5
2 1
2 3
4 -4
2 -1
3 5
```
## Sample Output 2
```
12
12
13
12
12
13
```
## Sample Input 3
```
7 5 10
-10 11 -15 -8 6 8 8
2 -16
6 -7
2 13
2 -18
4 -6
3 -8
4 10
5 7
2 -2
6 17
```
## Sample Output 3
```
6
7
10
8
9
8
6
10
8
7
7
```