#include <iostream>
#include <algorithm>
#include <assert.h>

using namespace std;

struct node {
    int depth;
    char *tail;
    char *delete_tail;
    node *children[2];
    node(int d, char *t = 0, int l = 0) {
        depth = d;
        children[0] = 0;
        children[1] = 0;
        if (t) {
            delete_tail = tail = new char[l];
            memcpy(tail, t, l);
        } else
            delete_tail = tail = 0;
    }
    void no_tail() {
        assert(tail);
        char bit = *tail;
        assert(!children[0]);
        assert(!children[1]);
        children[bit] = new node(depth + 1);
        children[bit]->delete_tail = delete_tail;
        children[bit]->tail = tail;
        delete_tail = 0;
        tail = 0;
    }
    ~node() {
        delete children[0];
        delete children[1];
        delete[] delete_tail;
    }
};

void random_id(char *id, int length) {
    while (length-- > 0) {
        *id++ = rand() % 2;
    }
}

int add_id(node *parent, char *tail, int size) {

    if (!size)
        return 0;

    char bit = *tail;
    assert(bit == 0 || bit == 1);

    if (parent->tail)
        parent->no_tail();

    if (!parent->children[bit]) {
        parent->children[bit] = new node(parent->depth + 1, tail + 1, size - 1);
        return parent->depth + 1;
    }

    return add_id(parent->children[bit], tail + 1, size - 1);
}

#define REPEATS 10
#define MAX_COMMON 64

int histogram[MAX_COMMON][REPEATS + 1];

void one_run(int run_num, int num_ids) {
    char id[128];
    random_id(id, sizeof(id));
    node root(0, id, sizeof(id));
    int longest = 0;
    for (int i = 1; i < num_ids; i++) {
        if (!(i % 1000))
            cerr << run_num << ' ' << i << ' ' << longest << '\r';
        random_id(id, sizeof(id));
        int common = add_id(&root, id, sizeof(id));
        if (common <= longest)
            continue;
        assert(longest < MAX_COMMON);
        int j = 0;
        while (histogram[longest][j])
            j++;
        histogram[longest][j] = i;
        cerr << run_num << ' ' << longest << " : " << i << endl;
        longest = common;
    }
    int j = 0;
    while (histogram[longest][j])
        j++;
    histogram[longest][j] = num_ids;
    cerr << run_num << ' ' << longest << " : " << num_ids << endl;
}


int main(int argc, const char * const * argv) {
    if (argc != 2) {
        cerr << "Usage: " << argv[0] << " number-of-ids" << endl;
        return 1;
    }
    int num_ids = atoi(argv[1]);
    for (int i = 0; i < REPEATS; i++)
        one_run(i, num_ids);

    for (int l = 0; l < MAX_COMMON; l++) {
        if (!histogram[l][0])
            continue;
        sort(histogram[l], histogram[l] + REPEATS, greater<int>());
        cout << l << " :";
        for (int r = 0; r < REPEATS && histogram[l][r]; r++)
            cout << ' ' << histogram[l][r];
        cout << endl;
    }
    return 0;
}