Description

由于出题者的疏忽，本题使用O(n log n)的算法可以在常数上吊打基数排序，故自行权衡

UPD：后来HYY大巨奆老使用了在 WC2017:挑战 中的做法，使用优化后的松式基排再次吊打了我，于是这道题又可以用了

很久以前，MZW在做一道LG上的题目时看到了一个很玄学的输入输出方法
然后他想来试一试。
这道题要求对一个数组排序，用你最快的方法。


本题提供以下模板：

#include <cstdio>
#include <cstring>
#include <algorithm>
unsigned long long rnd1, rnd2, rnd3;
unsigned int cnt;
inline unsigned long long rand1() {
	return rnd1 = rnd1 * 1994525ull + 1013904223ull;
}
inline unsigned long long rand2() {
	if((cnt & 0xffffff) == 0) rnd2 = rand1();
	return rnd2 = rnd2 * 1103515245ull + 12345ull;
}
inline unsigned long long rand3() {
	if((cnt & 0xfff) == 0) rnd3 = rand2();
	++cnt;
	return rnd3 = rnd3 * 214013ull + 2531011ull;
}
unsigned long long a[41110000];
int main() {
	unsigned long long n, seed, p;
	scanf("%lld%lld%lld", &n, &seed, &p);
	rnd1 = seed;
	for(register int i = 1; i <= n; i++)
		a[i] = rand3();
//std::sort(a + 1&#44; a + n + 1);

register unsigned long long ans = 0;
for(register int i = 1; i &lt;= n; i++)
	ans = ans * p + a[i];
printf("%llu"&#44; ans);
return 0;

}

您的排序程序将在标有注释std::sort的部分对数组进行排序
亦可以自行选择对IO部分进行优化
</p>

Input Format

三个64位正整数n,seed,p 
你的程序将用以下方法生成数据：

unsigned long long rnd1, rnd2, rnd3;
unsigned int cnt;
unsigned long long rand1() {return rnd1 = rnd1 * 1994525ull + 1013904223ull;}
unsigned long long rand2() {if((cnt & 0xffffff) == 0) rnd2 = rand1();