#include <iostream>
#include <vector>
#include <cmath>
#include <array>
using namespace std;


struct suffix
{
    int index; // To store original index
    int rank[2]; // To store ranks and next rank pair
};

bool operator<(const struct suffix& a, const struct suffix& b)
{
    if (a.rank[0] == b.rank[0])
    {
        if (a.rank[1] < b.rank[1])
            return true;
        else
            return false;
    }
    else if (a.rank[0] < b.rank[0])
        return true;
    else
        return false;

}

suffix* radix_sort(suffix A[], int n)
{
    int C[n];
    vector<suffix> B(n);

    int d, tmp, count;

    // Сортирую по столбцам рангов, сначала 0 потом 1
    for (int i = 0; i < 2; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            C[j] = 0;
        }

        for (int j = 0; j < n; ++j)
        {
            d = A[j].rank[i];
            C[d]++;
        }

        count = 0;
        for (int j = 0; j < n; ++j)
        {
            tmp = C[j];
            C[j] = count;
            count += tmp;
        }

        for (int j = 0; j < n; ++j)
        {
            d = A[j].rank[i];
            B[C[d]] = A[j];
            C[d]++;
        }

        for (int j = 0; j < n; ++j)
        {
            A[i] = B[i];
        }
    }

    cout << "12312321312";
    for (int i=0 ; i < 3; ++i)
    {
        cout << A[i].rank[0] << " " << A[i].rank[1] << endl;
    }

    return A;
}


int main()
{

    //13 31 22
    suffix arr[3];

    arr[0].rank[0] = 1;
    arr[0].rank[1] = 3;
    arr[1].rank[0] = 3;
    arr[1].rank[1] = 1;
    arr[2].rank[0] = 2;
    arr[2].rank[1] = 2;

    suffix* B = radix_sort(arr, 3);


    for (int i=0 ; i < 3; ++i)
    {
        cout << B[i].rank[0] << " " << B[i].rank[1] << endl;
    }


    return 0;
}