unsigned B[100000005],s[2047+1];
void radix_sort(unsigned *A,int l,int r){ //a[i]>=0
//const int base=65535,W=16;
const int base=2047,W=11;
//const int base=255,W=8;
const int T=(32-1)/W+1;
A+=l-1;r-=l-1;l=1;
unsigned *a=A,*b=B,x=0;
for (int i1=1;i1<=T;++i1){
for (int i=0;i<=base;++i)s[i]=0;
for (int i=1;i<=r;++i)++s[a[i]>>x&base];
for (int i=1;i<=base;++i)s[i]+=s[i-1];
for (int i=r;i>=1;--i)b[s[a[i]>>x&base]--]=a[i];
unsigned *tmp=a;a=b;b=tmp;
x+=W;
}
if (a!=A)for (int i=1;i<=r;++i)A[i]=a[i];
}