// 8-bit 4-pass LSD radix sort
typedef unsigned u32;
static u32 tmp[100000000];
static u32 cnt[256];
void sort(u32 *a, int n) {
u32 i;
for (i = 0; i < 256; i++) cnt[i] = 0;
for (i = 0; i < (u32)n; i++) cnt[a[i] & 255]++;
for (i = 1; i < 256; i++) cnt[i] += cnt[i-1];
for (i = (u32)n; i-- > 0;) tmp[--cnt[a[i] & 255]] = a[i];
for (i = 0; i < 256; i++) cnt[i] = 0;
for (i = 0; i < (u32)n; i++) cnt[(tmp[i] >> 8) & 255]++;
for (i = 1; i < 256; i++) cnt[i] += cnt[i-1];
for (i = (u32)n; i-- > 0;) a[--cnt[(tmp[i] >> 8) & 255]] = tmp[i];
for (i = 0; i < 256; i++) cnt[i] = 0;
for (i = 0; i < (u32)n; i++) cnt[(a[i] >> 16) & 255]++;
for (i = 1; i < 256; i++) cnt[i] += cnt[i-1];
for (i = (u32)n; i-- > 0;) tmp[--cnt[(a[i] >> 16) & 255]] = a[i];
for (i = 0; i < 256; i++) cnt[i] = 0;
for (i = 0; i < (u32)n; i++) cnt[tmp[i] >> 24]++;
for (i = 1; i < 256; i++) cnt[i] += cnt[i-1];
for (i = (u32)n; i-- > 0;) a[--cnt[tmp[i] >> 24]] = tmp[i];
}