// Мазырин
// Роман

/*
7_1. Быстрейшая сортировка.
Дан массив целых чисел в диапазоне [0..10^9]. Размер массива кратен 10 и ограничен сверху значением 2.5 * 10^7 элементов. Все значения массива являются элементами псевдо-рандомной последовательности. Необходимо отсортировать элементы массива за минимально время и вывести каждый десятый элемент отсортированной последовательности.
Минимальный набор оптимизаций, который необходимо реализовать:
1. Оптимизация ввода/вывода
2. Оптимизация выбора опорного элемента
3. Оптимизация Partition
4. Оптимизация рекурсии
5. Оптимизация концевой рекурсии
 */

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

//#define DBG

#ifdef DBG
#include <time.h>
#endif

using namespace std;

const int INSERTION_SORT_SIZE = 20;

struct Boundary {
    int left;
    int right;
    Boundary() : left(0), right(0) {};
    Boundary(int pLeft, int pRight) {
        left = pLeft;
        right = pRight;
    }
    Boundary(const Boundary& b) {
        left = b.left;
        right = b.right;
    }
};

class Stack {
private:
    Boundary* arr;
    int size;
    int tail;
public:
    Stack() : arr(0), tail(0), size(0) {};
    Stack(int beginSize) {
        tail = 0;
        size = beginSize;
        arr = new Boundary[beginSize]();
    }

    int getCount() {
        return tail;
    }

    void grow() {
        int newSize = size*2;
        Boundary* tempArr = new Boundary[newSize]();
        for( int i = 0; i < size; i++ ) {
            tempArr[i] = arr[i];
        }
        size = newSize;
        delete [] arr;
        arr = tempArr;
    }

    void push(Boundary b) {
        if( tail == size ) {
            grow();
        }
        arr[tail++] = b;
    }

    Boundary pop() {
        assert(tail > 0);
        return arr[--tail];
    }

    ~Stack() {
        delete [] arr;
    }

};

int findMedianIndex(int* arr, int left, int right) {
    int middleElemKey = (left+right)/2;
    if( (arr[left] >= arr[right] && arr[left] <= arr[middleElemKey]) ||
            (arr[left] >= arr[middleElemKey] && arr[left] <= arr[right]) ) {
        return left;
    } else {
        if( arr[middleElemKey] >= arr[right] ) {
            return right;
        } else {
            return middleElemKey;
        }
    }
}

void insertionSort(int* arr, int left, int right) {
    for(int i = left+1; i <= right; i++ ) {
        for( int j = i-1; (j >= left) && (arr[j] > arr[j+1]); j--) {
            swap(arr[j], arr[j+1]);
        }
    }
}

int partition(int* arr, int left, int right, int pivotPos) {
    swap(arr[right], arr[pivotPos]);
    int i = left;
    int j = left;
    while( j < right ) {
        if( arr[j] >= arr[right] ) {
            j++;
        } else {
            if( j != i ) {
                swap(arr[j], arr[i]);
            }
            i++;
            j++;
        }
    }
    swap(arr[i], arr[right]);
    return i;
}

void SuperQuickSort(int* arr, int size) {

    Stack intervals(1000);
    int left = 0;
    int right = size - 1;
    int pivot = 0;
    do {
        // Сортируем левые интервалы до тех пор, пока не дойдем до сортировки вставками, а правые пихаем в стек
        do {
            if( right - left <= INSERTION_SORT_SIZE ) {
                insertionSort(arr, left, right);
                break;
            }
            pivot = findMedianIndex(arr, left, right);
            pivot = partition(arr, left, right, pivot);
            intervals.push(Boundary(pivot+1, right));
            right = pivot;
        } while( true );

        // Начинаем сортировать правые стороны до тех пор, пока интервал не станет больше INSERTION_SORT_SIZE
        while( (right - left <= INSERTION_SORT_SIZE) && (right != size-1) ) {
            Boundary a = intervals.pop();
            left = a.left;
            right = a.right;
            if( right - left <= INSERTION_SORT_SIZE ) {
                insertionSort(arr, left, right);
            }
        }
        // До тех пор, пока есть интервалы в стеке или текущий интервал больше чем INSERTION_SORT_SIZE
    } while( intervals.getCount() > 0 || right-left > INSERTION_SORT_SIZE );
}

int main() {

    ios_base::sync_with_stdio(false);

    int* arr = new int[25000000];

    register int size = 0;
    while( scanf("%d", &arr[size]) == 1) {
        size++;
    }

    #ifdef DBG
    clock_t start = clock();

    SuperQuickSort(arr, size);
    for( int i = 9; i < size; i += 10 ) {
        printf("%d ", arr[i]);
    }

    printf("\n%f", (float)(clock()-start)/CLOCKS_PER_SEC);
    #endif

    #ifndef DBG
    SuperQuickSort(arr, size);
    for( int i = 9; i < size; i += 10 ) {
        printf("%d ", arr[i]);
    }
    #endif

    delete [] arr;
    return 0;
}