#include <cstring>
unsigned b[65536], c[100000000];
void sort(unsigned *a, int n) {
for (int i = 0; i < n; ++i) ++b[a[i] & 65535];
for (int i = 1; i < 65536; ++i) b[i] += b[i - 1];
for (int i = n - 1; i >= 0; --i) c[--b[a[i] & 65535]] = a[i];
memset(b, 0, sizeof b);
for (int i = 0; i < n; ++i) ++b[c[i] >> 16];
for (int i = 1; i < 65536; ++i) b[i] += b[i - 1];
for (int i = n - 1; i >= 0; --i) a[--b[c[i] >> 16]] = c[i];
}