#include <iostream>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cmath>


typedef struct Tdata {
    unsigned long long key;
    char value[65];
} T_data;


typedef struct Tlist {
    struct Tlist * next;
    struct Tlist * prev;
    struct Tdata data;
    bool isEmpty;
} T_list;


Tlist * Create (Tlist * list) {
    Tlist * newlist = new Tlist;
    newlist->prev = NULL;
    newlist->next = NULL;
    newlist->isEmpty = true;
    return newlist;
}

void Append_to_list (Tdata data, Tlist * list) {
    unsigned long long x = data.key;
    bool isFirst = false, isLast = false;
    if (list->isEmpty) {
        list->data = data;
        list->isEmpty = false;
        return;
    }
    else {
        Tlist * newlist = new Tlist;
        Tlist * temp = new Tlist;
        newlist->data = data;
        if (x < list->data.key) {
            while (x < list->data.key) {
                temp = list;
                list = list->prev;
                if (list == NULL) {
                    isFirst = true;
                    break;
                }
            }
            if (isFirst) {
                newlist->prev = NULL;
                newlist->next = temp;
                temp->prev = newlist;
            }
            else {
                newlist->prev = list;
                newlist->next = list->next;
                list->next->prev = newlist;
                list->next = newlist;
            }
            return;

        }
        else if (x >= list->data.key) {
            while (x >= list->data.key) {
                temp = list;
                list = list->next;
                if (list == NULL) {
                    isLast = true;
                    break;
                }
            }
            if (isLast) {
                newlist->next = NULL;
                newlist->prev = temp;
                temp->next = newlist;
            }
            else {
                newlist->next = list;
                newlist->prev = list->prev;
                list->prev->next = newlist;
                list->prev = newlist;
            }
            return;
        }
    }
}

Tdata * Bucket_Sort (Tdata *array, Tlist ** list_array, int array_size, unsigned long long const_frag, int number_of_lists) {
    int * list_size = new int[array_size];
    for (int i = 0; i < number_of_lists; i++) { // or array_size
        list_array[i] = Create(list_array[i]);
        list_size[i] = 0;
    }
    for (int i = 0; i < array_size; i++) {
        int list_num = 0;
        unsigned long long frag = const_frag;
        while (1) {
            if (array[i].key <= frag) {
                Append_to_list(array[i], list_array[list_num]);  // adding Tdata struct
                list_size[i]++;
                break;
            }
            else {
                frag += const_frag;
                list_num++;
                if (list_num +1 ==  number_of_lists) { //array_size
                    frag = ULLONG_MAX;
                }
            }
        }
    }
    int list_num = 0;
    int i = 0;

    for (int j = 0; j < number_of_lists; j++) { // array_size
        if (list_array[list_num]->isEmpty == false) {
            while (list_array[list_num]->prev != NULL) {
                list_array[list_num] = list_array[list_num]->prev;
            }
            while (list_array[list_num] != NULL) {
                array[i] = list_array[list_num]->data;
                i++;
                list_array[list_num] = list_array[list_num]->next;
            }
        }
        list_num++;
    }
    return array;
}


int main() {

    Tdata * array = (Tdata*) std::malloc(10 * sizeof(Tdata));
    int array_size = 0;
    int current_size = 10;

    unsigned long long key;
    char value[65];

    while (std::cin >> key >> value) {
        array[array_size].key = key;
       // std::cout << value << std::endl;
        strcpy(array[array_size].value, value);
        array_size++;
        if (array_size+1 == current_size) {
            int new_size = array_size * 2;
            current_size = new_size;
            array = (Tdata *) std::realloc(array, new_size * sizeof(Tdata));
        }
    }

    int number_of_lists = array_size;
    unsigned long long frag;
    if (array_size != 0) {
        frag = ULLONG_MAX /number_of_lists; // or / array_size
    }
    else {
        return 0;
    }
    // sort

    Tlist ** list_array = new Tlist * [number_of_lists];
    unsigned int start_time =  clock();
    array = Bucket_Sort(array, list_array, array_size, frag, number_of_lists);
    unsigned int end_time = clock(); // конечное время
    unsigned int search_time = end_time - start_time; // искомое время
    for (int i = 0; i < array_size; i++) {
        std::cout << array[i].key << "\t" << array[i].value << std::endl;
    }
    std::cout << search_time <<std::endl;
    delete array;
    delete list_array;

    return 0;
}