Background

Our capital, Gracemeria, is under attack by an unknown force.

The destruction caused by the air raid has spread across the whole city.

All aircraft, scramble immediately to intercept.

---

"Garuda 1, you are cleared for takeoff."

...

"Garuda 1, take off. Cerberus team, the runway is clear. Take off when ready."

"After all aircraft are airborne, follow AWACS commands."

"This is not a drill. I repeat, this is not a drill!"

...

"This is AWACS Ghost Eye."

...

"Garuda 1, you have no wingman."

"Let me see... Shamrock."

"You are flying solo too, right?"

"Good. From now on, you are Garuda 2."

"Hello, this is Garuda 2."

"No time for introductions. Hurry. Garuda 1, accelerate. I will follow."

"Just give me orders."

"Garuda team, you may now engage the enemy over Gracemeria."

...

"May the Golden King smiles on us！！"

$$_{{\frac{\large\text{ACE COMBAT }\Large6}{\tiny{\text{F i r e s\quad O f\quad L i b e r a t i o n}}}}}\\ \text{Mission 01} \\\Large\text{Invasion Of Gracemeria}\\\tiny -\textit{ Through the Heart Of a Nation }-$$

Problem Description

You are given a sequence $a$ of length $n$, initially all $0$, and a positive integer $k$.

There are $q$ operations. Each operation gives $i, v$, meaning to add $v$ to the suffix $a_{[i,n]}$ of the sequence $a$.

After each operation, output the result of the sum of the $k$-th powers of the occurrence counts of all values in the sequence, modulo $20051131$.

$20051131$ is a prime number.

Input Format

The first line contains three integers $n, q, k$.

The next $q$ lines each contain two integers, representing the operation $i, v$.

Output Format

Output $q$ lines, each containing one integer: after this operation, the sum of the $k$-th powers of the occurrence counts of all values in the sequence, modulo $20051131$.

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

25
17
11
7
5

Hint

After the first operation, there are $5$ occurrences of $1$, so the answer is $5^2 = 25$.

After the second operation, there are $1$ occurrence of $1$ and $4$ occurrences of $2$, so the answer is $1^2 + 4^2 = 17$.

Similarly, the answers are $1^2 + 1^2 + 3^2 = 11$, $1^2 + 1^2 + 1^2 + 2^2 = 7$, and $5 \times 1^2 = 5$.

---

• Subtask 1 (20 pts): $n, q \leq 2 \times 10^3$.
• Subtask 2 (40 pts): $n \leq 2 \times 10^3$.
• Subtask 3 (40 pts): no special constraints.

For $100\%$ of the testdata, it is guaranteed that $1 \leq n, v, k \leq 20051130$, $1 \leq q \leq 5 \times 10^5$, and $1 \leq i \leq n$.

idea: Sol1, solution: Sol1, code: Sol1, data: Sol1 & Xielan Canxiao (pinyin).

Translated by ChatGPT 5