「MCOI-Zero / AC6-M01」Invasion of Gracemeria

题目背景

我们的首都 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 }-$$ ![](https://cdn.luogu.com.cn/upload/image_hosting/nd20pe59.png)

题目描述

给定一个长度为 $n$ 的序列 $a$,初始都是 $0$,和一个正整数 $k$。 现有 $q$ 次操作,每次操作给定 $i,v$,表示给序列 $a$ 的后缀 $a_{[i,n]}$ 加上 $v$。 每次操作后,请你输出 **所有数在序列中出现次数的 $k$ 次方和** 对 $20051131$ 取模的结果。 $20051131$ 是质数。

输入输出格式

输入格式


第一行三个整数 $n,q,k$。 接下来 $q$ 行,每行两个整数,表示这次操作的 $i,v$。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #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 & 斜揽残箫