题目背景

我们的首都 Gracemeria 正在遭受不明势力袭击！

空袭造成的破坏遍布全城。

全机，立刻紧急升空迎击！

---

「Garuda 1，你可以起飞了。」

……

「Garuda 1，升空。Cerberus 队，跑道已经清空，你们准备好了就起飞。」

「所有飞机升空后听从 AWACS 的命令。」

「这不是演习。重复一遍，这不是演习！」

……

「这里是 AWACS Ghost Eye。」

……

「Garuda 1，你没僚机。」

「让我看看……
　Shamrock。」

「你也是单机一架，对吗？」

「很好。
　从现在起你就是 Garuda 2 了。」

「你好，这里是 Garuda 2。」

「没时间自我介绍了，快。
　Garuda 1，加速，我会跟上。」

「尽管给我命令就好。」

「Garuda 队，你们已经可以同 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 }- $$

题目描述

给定一个长度为 $n$ 的序列 $a$，初始都是 $0$，和一个正整数 $k$。

现有 $q$ 次操作，每次操作给定 $i,v$，表示给序列 $a$ 的后缀 $a_{[i,n]}$ 加上 $v$。

每次操作后，请你输出 所有数在序列中出现次数的 $k$ 次方和 对 $20051131$ 取模的结果。

$20051131$ 是质数。

输入格式

第一行三个整数 $n,q,k$。

接下来 $q$ 行，每行两个整数，表示这次操作的 $i,v$。

输出格式

$q$ 行，每行一个整数，表示这次操作之后所有数在序列中出现次数的 $k$ 次方和对 $20051131$ 取模的值。

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

25
17
11
7
5

提示

第一次操作后，有 $5$ 个 $1$，答案为 $5^2=25$。

第二次操作后，有 $1$ 个 $1$ 和 $4$ 个 $2$，答案为 $1^2+4^2=17$。

类似的，答案分别为 $1^2+1^2+3^2=11,1^2+1^2+1^2+2^2=7,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）：无特殊限制。

对 $100\%$ 的数据，保证 $1\leq n,v,k\leq 20051130$，$1\leq q\leq 5\times 10^5$，$1\leq i\leq n$。

idea：Sol1，solution：Sol1，code：Sol1，data：Sol1 & 斜揽残箫