Welcome Back Contest: 2025 Problem 3

Sally loves taking photos of the wonderful buildings in her town! There are ~N~ buildings standing next to each other, numbered ~1~ to ~N~ from left to right. She wants assign a "view score" for the view of the buildings using her camera. Sally's camera can capture up to ~K~ adjacent buildings together in a single photo. In order to score the view the buildings, she first takes pictures of all sets of ~K~ adjacent buildings. By doing this, she will have taken ~N - K + 1~ photos. For each photo, she defines its individual "score" as the sum of the heights of each building in the photo. She then takes the sum of all scores and calls it the view score.

However, the heights of various buildings may change due to construction. In total, ~U~ updates happen to various buildings. For each of the ~U~ updates, a building increases their height by some amount. Since Sally wants to keep her view score up to date, after each update, she recomputes the view score by repeating her initial process.

Help Sally calculate the view score after each of the ~U~ updates, as well as the original score.

Input Specification

The first line contains the integers ~N~, ~K~, and ~U~, each separated by a single space.

The next line contains the intial heights of the ~N~ buildings, each separated by a single space. The ~i~-th building has an initial height of ~h_i~.

The next ~U~ lines contain ~2~ integers each, ~i~ and ~v~, indicating that the ~i~-th building increased by a height of ~v~.

Output Specification

On the first line, output the initial view score. For each of the ~U~ updates, output the new view score on its own line.

Subtasks

~1 \le K \le N \le 10^5~

~1 \le U \le 10^5~

~1 \le h_i, v \le 100~

Subtask 1 [50%]

~1 \le K \le N \le 1000~

~1 \le U \le 1000~

Subtask 2 [50%]

No additional constraints

Sample Input 1

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

Output for Sample Input 1

25
27
33

Explanation of Output for Sample Input 1

Initially, there are ~5~ buildings of heights ~[3, 5, 2, 1, 4]~.

First, Sally takes photos of all possible groupings of ~3~ adjacent buildings, which are of ~[3, 5, 2]~, ~[5, 2, 1]~, and ~[2, 1, 4]~. The sums of the pictures are ~10~, ~8~, and ~7~. Thus, the view score is ~10 + 8 + 7 = 25~.

After the first update, the ~2~nd building increased its height by ~1~. The ~5~ buildings now have a heights of ~[3, 6, 2, 1, 4]~. The new view score is ~11 + 9 + 7 = 27~.

After the second update, the ~3~rd building increased its height by ~2~. The ~5~ buildings now have a heights of ~[3, 6, 4, 1, 4]~. The new view score is ~13 + 11 + 9 = 33~.

Sample Input 2

4 3 3
1 1 1 1
4 1
1 1
2 1

Output for Sample Input 2

6
7
8
10

Sample Input 3

6 3 1
1 2 3 4 5 6
1 1

Output for Sample Input 3

42
43