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