#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <functional>
#include <map>

using namespace std;

//метод update для построения графа: компонента связности = станция
//трелки идут от более ранних электричек к более поздним

//color: 0 - белый, 1 - серый, 2 - черный
void dfs(int v, vector <vector <int> > & gr, vector <int>& TopSort, vector <int>& color) {
    if (color[v] == 2) return;
    color[v] = 1;
    for (int u : gr[v]) {
        dfs(u, gr, TopSort, color);
    }
    color[v] = 2;
    TopSort.push_back(v);
}


int main()
{
    int N;
    //cin >> N;
    //N = rand() % 10 + 1;
    N = 6;
    cout << "N = " << N << '\n';
    map <int, vector <pair <int, int> > > railway; // double - time through; int - vertex (station)
    for (int i = 1; i < N + 1; ++i) {

        int A, B=0, C, D=0;
        //cin >> A >> B >> C >> D;
        A = rand() % 10 + 1;
        while (B<=A) B = rand() % 10 + 1;
        C = rand() % 10 + 1;
        D = rand() % 10 + 1;
        cout << A << "  " << B << "  " << C << "  " << D << '\n';
        int t_A = C;
        int t_B = C + (B - A) * D;
        cout << "t_A = " << t_A << "   t_B = " << t_B << '\n';
        //cout << "Tin = " << t_A << "   Tout = " << t_B << '\n';
        pair <int, int> new_A;
        int train = i;
        new_A.first = t_A;
        new_A.second = train;
        //заполняем наш map railway
        vector <pair <int, int> > new_vec_A = { new_A };
        if (railway.find(A) == railway.end()) railway.insert(make_pair(A, new_vec_A));
        else railway[A].push_back({ t_A, train });
        pair <int, int> new_B;
        new_B.first = t_B;
        new_B.second = train;
        vector <pair <int, int> > new_vec_B = { new_B };
        if (railway.find(B) == railway.end()) railway.insert(make_pair(B, new_vec_B));
        else railway[B].push_back({ t_B, train });

    }cout << '\n';
    for (auto el : railway) {
        auto station = el.first;
        sort(railway[station].begin(), railway[station].end());
    }
    //теперь  создадим граф
    vector <vector <int> > gr(N + 1);
    for (auto el : railway) {
        int station = el.first; //электрички, побывавшие на этой станции, уже отсортированы в порядке воозрастания
        int sz = (int)el.second.size();
        vector <pair <int, int> > order = el.second;
        for (int i = 0; i < sz - 1; ++i) {
            int v_from = order[i].second; //побывала на станции раньше
            int v_to = order[i + 1].second;
            gr[v_from].push_back(v_to);
        }
    }
    //теперь делаем TopSort
    vector <int> TopSort;
    vector <int> color(N + 1, 0);
    for (int i = 1; i < N + 1; ++i) {
        dfs(i, gr, TopSort, color);
    }
    reverse(TopSort.begin(), TopSort.end());
    for (int i = 0; i < TopSort.size(); ++i) {
        cout << TopSort[i] << ' ';
    }cout << '\n';
    /*for (int i = 1; i < gr.size(); ++i) {
        cout << "from = " <<i<< '\n' << "to = " << '\n';
        for (int j = 0; j < gr[i].size(); ++j) {
            cout<<gr[i][j] << ' ';
        }cout << '\n';
    }*/

    /*for (auto el : railway) {
        cout << "station = " << el.first << '\n';
        cout << "info = "  << '\n';
        for (auto to : el.second) cout << to.first <<"  "<<to.second << '\n';
        cout << '\n';
    }*/
        cout << "done\n";
}