「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 }-$$ 

给定一个长度为 $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 & 斜揽残箫