该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小 A 想要生成一个数列！

目前他已有 $n$ 个整数 $a_1\sim a_n$，他希望再添加 $m$ 个数到数列中，他会按照下面的方式一个一个地添加：

• 先找到当前所有整数的中位数 $mid$，然后添加 $(mid\times mid)\% P$ 到数列中。
• （$P$ 为一个已知的整数，$\%$ 为取余）。

最终小 A 会得到一个长度为 $n+m$ 的数列，如果输出这么大的数列太费时间了，因此他希望你告诉他所有数之和对 $P$ 取余后的值。

本题中位数的定义：对于 $len$ 个元素的序列，将其从小到大排列后，第 $\lfloor \frac{len+1}{2} \rfloor$ 个元素即中位数。$\lfloor\ \rfloor$ 的意思是下取整。

输入格式

第一行为空格隔开的两个整数 $n,m,P$。
接下来一行 $n$ 个整数，即 $a_1\sim a_n$。

输出格式

一行一个整数，为”最终 $n+m$ 个数之和”对 $P$ 取余后的结果。

4 4 998244353
1 2 3 4

48 

样例 1 解释

• 1 2 3 4 中位数为 2，新添加的数为 4
• 1 2 3 4 4 中位数为 3，新添加的数为 9
• 1 2 3 4 4 9 中位数为 3，新添加的数为 9
• 1 2 3 4 4 9 9 中位数为 4，新添加的数为 16
• 最终序列为：1 2 3 4 4 9 9 16，$1+2+3+4+4+9+9+16=48$，所以输出 $48\%998244353 = 48$

数据规模与约定

对于所有数据，保证 $1\le a_i\le 10^6$，$P=998244353$

• 子任务 1（25 分）：$1\le n,m\le 2000$。
• 子任务 2（25 分）：$1\le n,m\le 10^4$。
• 测试点 3（25 分）：$1\le n,m\le 10^6$。
• 测试点 4（25 分）：$n=1$，$1\le m\le 10^{12}$