const unsigned int m=16,M=65535;
unsigned int b[100000000],cnt[66666],cnt2[66666];
void sort(unsigned *a, int n)
{
for(register int i=n;i--;) ++cnt[a[i]&M];
for(register int i=0;i++<M;) cnt[i]+=cnt[i-1];
for(register int i=n;i--;) b[--cnt[a[i]&M]]=a[i];
for(register int i=n;i--;) ++cnt2[b[i]>>m];
for(register int i=0;i++<M;) cnt2[i]+=cnt2[i-1];
for(register int i=n;i--;) a[--cnt2[b[i]>>m]]=b[i];
}