#include <cstring>
const unsigned N = 1e8 + 5;
unsigned aux[N];
void sort(unsigned *a, int n) {
const unsigned U = 256;
unsigned cnt[U];
memset(cnt, 0, sizeof cnt);
for (unsigned i = 0; i < n; ++i)
++cnt[a[i] & U - 1];
for (unsigned i = 1; i < U; ++i)
cnt[i] += cnt[i - 1];
for (unsigned i = n - 1; i >= 0; --i)
aux[--cnt[a[i] & U - 1]] = a[i];
memset(cnt, 0, sizeof cnt);
for (unsigned i = 0; i < n; ++i)
++cnt[aux[i] >> 8 & U - 1];
for (unsigned i = 1; i < U; ++i)
cnt[i] += cnt[i - 1];
for (unsigned i = n - 1; i >= 0; --i)
a[--cnt[aux[i] >> 8 & U - 1]] = aux[i];
memset(cnt, 0, sizeof cnt);
for (unsigned i = 0; i < n; ++i)
++cnt[a[i] >> 16 & U - 1];
for (unsigned i = 1; i < U; ++i)
cnt[i] += cnt[i - 1];
for (unsigned i = n - 1; i >= 0; --i)
aux[--cnt[a[i] >> 16 & U - 1]] = a[i];
memset(cnt, 0, sizeof cnt);
for (unsigned i = 0; i < n; ++i)
++cnt[aux[i] >> 24];
for (unsigned i = 1; i < U; ++i)
cnt[i] += cnt[i - 1];
for (unsigned i = n - 1; i >= 0; --i)
a[--cnt[aux[i] >> 24]] = aux[i];
}