#define ui unsigned
ui b[1<<27|5],sd;
int c0[256],c1[256],c2[256],c3[256];
void sort(ui*a,int n)
{
for(ui *i=a,*j=a+n;i!=j;++i){
sd=*i;
++c0[sd&255];
++c1[sd>>8&255];
++c2[sd>>16&255];
++c3[sd>>24&255];
}
for(int i=1;i<256;++i){
c0[i]+=c0[i-1];
c1[i]+=c1[i-1];
c2[i]+=c2[i-1];
c3[i]+=c3[i-1];
}
int i=n>>3;
ui*p=a+n-1;
while(i--){
b[--c0[p[0]&255]]=p[0];
b[--c0[p[-1]&255]]=p[-1];
b[--c0[p[-2]&255]]=p[-2];
b[--c0[p[-3]&255]]=p[-3];
b[--c0[p[-4]&255]]=p[-4];
b[--c0[p[-5]&255]]=p[-5];
b[--c0[p[-6]&255]]=p[-6];
b[--c0[p[-7]&255]]=p[-7];
p-=8;
}
switch(n&7){
case 7:b[--c0[*p&255]]=*p,--p;
case 6:b[--c0[*p&255]]=*p,--p;
case 5:b[--c0[*p&255]]=*p,--p;
case 4:b[--c0[*p&255]]=*p,--p;
case 3:b[--c0[*p&255]]=*p,--p;
case 2:b[--c0[*p&255]]=*p,--p;
case 1:b[--c0[*p&255]]=*p,--p;
}
i=n>>3;p=b+n-1;
while(i--){
a[--c1[p[0]>>8&255]]=p[0];
a[--c1[p[-1]>>8&255]]=p[-1];
a[--c1[p[-2]>>8&255]]=p[-2];
a[--c1[p[-3]>>8&255]]=p[-3];
a[--c1[p[-4]>>8&255]]=p[-4];
a[--c1[p[-5]>>8&255]]=p[-5];
a[--c1[p[-6]>>8&255]]=p[-6];
a[--c1[p[-7]>>8&255]]=p[-7];
p-=8;
}
switch(n&7){
case 7:a[--c1[*p>>8&255]]=*p,--p;
case 6:a[--c1[*p>>8&255]]=*p,--p;
case 5:a[--c1[*p>>8&255]]=*p,--p;
case 4:a[--c1[*p>>8&255]]=*p,--p;
case 3:a[--c1[*p>>8&255]]=*p,--p;
case 2:a[--c1[*p>>8&255]]=*p,--p;
case 1:a[--c1[*p>>8&255]]=*p,--p;
}
i=n>>3;
p=a+n-1;
while(i--){
b[--c2[p[0]>>16&255]]=p[0];
b[--c2[p[-1]>>16&255]]=p[-1];
b[--c2[p[-2]>>16&255]]=p[-2];
b[--c2[p[-3]>>16&255]]=p[-3];
b[--c2[p[-4]>>16&255]]=p[-4];
b[--c2[p[-5]>>16&255]]=p[-5];
b[--c2[p[-6]>>16&255]]=p[-6];
b[--c2[p[-7]>>16&255]]=p[-7];
p-=8;
}
switch(n&7){
case 7:b[--c2[*p>>16&255]]=*p,--p;
case 6:b[--c2[*p>>16&255]]=*p,--p;
case 5:b[--c2[*p>>16&255]]=*p,--p;
case 4:b[--c2[*p>>16&255]]=*p,--p;
case 3:b[--c2[*p>>16&255]]=*p,--p;
case 2:b[--c2[*p>>16&255]]=*p,--p;
case 1:b[--c2[*p>>16&255]]=*p,--p;
}
i=n>>3;
p=b+n-1;
while(i--){
a[--c3[p[0]>>24&255]]=p[0];
a[--c3[p[-1]>>24&255]]=p[-1];
a[--c3[p[-2]>>24&255]]=p[-2];
a[--c3[p[-3]>>24&255]]=p[-3];
a[--c3[p[-4]>>24&255]]=p[-4];
a[--c3[p[-5]>>24&255]]=p[-5];
a[--c3[p[-6]>>24&255]]=p[-6];
a[--c3[p[-7]>>24&255]]=p[-7];
p-=8;
}
switch(n&7){
case 7:a[--c3[*p>>24&255]]=*p,--p;
case 6:a[--c3[*p>>24&255]]=*p,--p;
case 5:a[--c3[*p>>24&255]]=*p,--p;
case 4:a[--c3[*p>>24&255]]=*p,--p;
case 3:a[--c3[*p>>24&255]]=*p,--p;
case 2:a[--c3[*p>>24&255]]=*p,--p;
case 1:a[--c3[*p>>24&255]]=*p,--p;
}
}