题目描述

33DAI 定义了一个函数：

int seed, P; // 通过输入得到
int f(int id)
{
    return 1LL * id * id % P * seed % P;
}

33DAI 用这个函数生成了一个长度为 $n$ 序列 $a$，下标从 $1\sim n$，第 $i$ 个数 $a_i$ 的值为 $f(i)$。

请你将这个序列排序，保证每个数都大于或等于它后面的数，即 $a_1\ge a_2\ge \dots \ge a_n$。

然后输出“每个元素与其下标之和”的异或和。即排序后的 $(a_1+1)\oplus (a_2+2)\oplus \dots\oplus (a_n+n)$ 。

异或：数学中用 $\oplus$ 符号表示异或和，C++ 中可以使用 a^b 算出两个数的异或和。由于异或和运算属于位运算，优先级非常低，建议所有涉及位运算的表达式都多用小括号来保证运算符优先级正确。

输入格式

输入三个整数 $n,seed,P$。

输出格式

输出题目要求的“每个元素与其下标之和”的异或和。

5 33 100

92

样例解释

得到的序列为 $\{33,32,97,28,25\}$，排序后为 $\{97,33,32,28,25\}$

$(97+1)\oplus(33+2)\oplus(32+3)\oplus(28+4)\oplus(25+5)=92$

5000000 33 998244353

1069767311

数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 5\times 10^6$，$1\le seed,P\le 10^9$。

• 子任务 1（30 分）：保证 $n=1$。
• 子任务 2（30 分）：保证 $n\le 1000$。
• 子任务 3（40 分）：没有特殊限制