Description

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

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

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

$20051131$ 是质数。

Input Format

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

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

Output Format

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

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

25
17
11
7
5

Hint

第一次操作后，有 $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 & 斜揽残箫