Untitled

#include <iostream>
#include <vector>

const int BASE = 10;
const int MAX_DIGIT_COUNT = 20;

struct KeyValuePair {
    uint64_t key;
    uint64_t value;
};

uint64_t binPow(uint64_t number, uint64_t power) {
    uint64_t result = 1;
    while (power != 0) {
        if (power & 1) result *= number;
        number *= number;
        power >>= 1;
    }
    return result;
}

void countSort(const std::vector<KeyValuePair>& keyValuePairsInput,
                     std::vector<KeyValuePair>& keyValuePairsOutput,
                     int digitIndex) {
    std::vector<uint64_t> counterVector(BASE, 0);
    for (auto keyValuePair : keyValuePairsInput) {
        int digit = (keyValuePair.key / binPow(BASE, digitIndex)) % BASE;
        ++counterVector[digit];

    }



    std::vector<uint64_t> prefixSumVector(BASE, 0);
    for (uint64_t i = 1; i < BASE; ++i) {
        prefixSumVector[i] = prefixSumVector[i - 1] + counterVector[i - 1];
    }

    for (auto keyValuePair: keyValuePairsInput) {
        int digit = (keyValuePair.key / binPow(BASE, digitIndex)) % BASE;
        keyValuePairsOutput[prefixSumVector[digit]++] = keyValuePair;
        --counterVector[digit];
    }
}


void radixSort(std::vector<KeyValuePair>& keyValuePairsInput,
               std::vector<KeyValuePair>& keyValuePairsOutput) {
    for (int i = 0; i < MAX_DIGIT_COUNT; ++i) {
        countSort(keyValuePairsInput, keyValuePairsOutput, i);
        keyValuePairsInput = keyValuePairsOutput; 
    }
}


int main() {    
    std::vector<KeyValuePair> keyValuePairsInput; // Здесь хранятся пары ключ-значение, которые мы получаем при вводе данных
    KeyValuePair pair;
    while(std::cin >> pair.key && std::cin >> pair.value) {
        keyValuePairsInput.push_back(pair);
    }

    std::vector<KeyValuePair> keyValuePairsOutput(keyValuePairsInput.size()); // Здесь хранятся пары ключ-значение, которые мы будем выводить(Он отсортирован)

    radixSort(keyValuePairsInput, keyValuePairsOutput);
    for (auto keyValuePair : keyValuePairsOutput) {
        std::cout << keyValuePair.key << '\t' << keyValuePair.value << std::endl;
    }

    return 0;
}