The cafeteria has introduced new dishes! To encourage students to try them, the cafeteria is offering vouchers, each worth $1$ yuan. After hearing this news, Kele decided to go to the cafeteria to taste the new dishes. The rules for using the vouchers are as follows:

• For every $c$ yuan Kele spends, she receives one voucher. Any remaining amount less than $c$ is ignored.
• These vouchers can be used in any subsequent meal to reduce the actual payment for that meal by $1$ yuan. Note that the portion paid using vouchers does not count towards Kele's spending.
• If Kele purchases a dish worth $a$ yuan, she can use at most $a$ vouchers.
• Kele only uses vouchers she has already earned through spending; she starts with zero vouchers.

In other words, if Kele purchases dishes totaling $a$ yuan and uses $b$ vouchers, she only needs to pay $a-b$ yuan, and she will receive $\lfloor \frac{a-b}{c} \rfloor$ vouchers.

Kele plans to taste $n$ new dishes in order, where the $i$-th dish costs $a_i$ yuan. Kele wants to know the minimum amount of money she needs to spend.

Since Kele is a shrewd girl, she often changes her plans. She also wants to know the minimum amount she needs to spend after each plan change.

Input

The first line contains three positive integers $n, Q, c$.

The next line contains $n$ positive integers, where the $i$-th integer represents $a_i$.

The next $Q$ lines each contain two positive integers $x_i, y_i$, representing a plan change where Rikka changes the $x_i$-th dish to one that costs $y_i$ yuan.

Output

The first line contains a positive integer representing the minimum cost for Kele's initial tasting plan.

The next $Q$ lines each contain a positive integer representing the minimum cost for Kele after the $i$-th plan change.

Examples

Input 1

5 5 4
23 38 19 37 14
1 12
2 17
3 41
4 33
5 18

Output 1

106
96
80
97
94
97

Input 2

5 5 3
9 8 7 6 5
1 19
2 18
3 17
4 16
5 15

Output 2

27
34
42
49
57
64

Subtasks

Subtask $1$ ($5\%$): $1 \le n, Q \le 5, 1 \le a_i, c, y \le 20$.

Subtask $2$ ($6\%$): $1 \le n, Q \le 20, 1 \le a_i, c, y \le 100$.

Subtask $3$ ($12\%$): $1 \le n, Q \le 500, 1 \le a_i, c, y \le 100000$.

Subtask $4$ ($17\%$): $1 \le n, Q \le 5000$.

Subtask $5$ ($11\%$): $c=1$.

Subtask $6$ ($15\%$): $c=2$.

Subtask $7$ ($11\%$): $a_i$ is generated uniformly at random in $[1, r]$, where $1 \le r \le 10^{12}$.

Subtask $8$ ($23\%$): No special restrictions.

For all test data, $1 \le n, Q \le 3 \times 10^5, 1 \le a_i, y \le 10^{12}, 1 \le c \le 10^9$.