#include <cstdio>
#include <string>
#include <cstdlib>
#define maxn 1000001
int a[maxn], aux[maxn];
int n;
const int T =(1<<10);
inline void rad(int n, int byte, int a[], int b[]) 
{
	int count[T], index[T],i;
	memset(count, 0, sizeof(count));
	
	for(i=0;i<n;++i) ++count[(a[i]>>byte)&(1023)];
	index[0]=0;
	for(i=1;i<T;++i) index[i]=index[i-1]+count[i-1];
	for(i=0;i<n;++i) b[index[(a[i]>>byte)&(1023)]++]=a[i];
}

inline void radix(int n, int a[])
{
	rad(n, 0, a, aux);
	rad(n, 10, aux, a);
	rad(n, 20, a, aux);
	for(int i=0;i<n;++i) a[i]=aux[i];
	//rad(n, 24, aux, a);
}

int main()
{
	int i;
	n=1000000;
	srand(time(0));
	for(i=0;i<n;++i)a[i]=rand()%123456672;
//	for(i=0;i<n;++i) printf("%d ", a[i]);
//	printf("\n");
	
	
	radix(n, a);
	
//	for(i=0;i<n;++i) printf("%d ", a[i]);
	return 0;
}