1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;

using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define int long long

const int INF = 1e18;

void solve(int _id) {
    int n, k, M;
    cin >> n >> k >> M;

    vector< vector< tuple<int, int> > > zelki_col(k);
    vector< tuple<int, int, int> > zelki;
    vector< pair<int, int> > col_min(k, {INF, INF});

    for (int i = 0; i < n; i++) {
        int k, m, c;
        cin >> k >> m >> c;
        k--;
        col_min[k] = min(col_min[k], {c, m});
        zelki.emplace_back(k, m, c);
        zelki_col[k].emplace_back(c, m);
    }

    sort(zelki.begin(), zelki.end());

    vector<int> res(M, INF);
    vector<int> dp(M, INF), dp2(M, INF);

    dp[0] = dp2[0] = 0;
    for (int i = 0; i < k; i++) {
        auto [min_c, min_m] = col_min[i];
        for (auto [c, m] : zelki_col[i]) {
            int tmp_c = c - min_c, tmp_m = (m - min_m + M) % M;

            for (int j = M - 1; j >= 0; j--) {
                dp2[j] = min(dp2[j], dp[ (j - tmp_m + M) % M ] + tmp_c);
            }
        }
        dp = dp2;
    }
    vector<int> dp_layer = dp;

    int min_sum_c = 0, min_sum_m = 0;

    for (int i = 0; i < k; i++) {
        auto [c, m] = col_min[i];

        if (c == INF) {
            cout << "0\n";
            for (int j = 0; j < M - 1; j++)
                cout << "-1\n";
            return;
        }

        min_sum_c += c;
        min_sum_m += m;
        min_sum_m %= M;
    }

    int act_c = 0, act_m = 0;
    unordered_set<int> zmienione1, zmienione2;

    for (int i = 0; i < M; i++)
        if (dp[i] < INF)
            zmienione1.insert(i);

    for (int i_ = 0; i_ < M; i_++) {
        act_c += min_sum_c;
        act_m += min_sum_m;
        if (act_m > M)
            act_m -= M;

        res[act_m] = min(res[act_m], act_c);

        for (int i = 0; i < M; i++) {
            int next = act_m + i;
            if (next >= M)
                next -= M;

            res[next] = min(res[next], act_c + dp[i]);
        }

        zmienione2.clear();
        for (int i : zmienione1) {
            for (int j = 0; j < M; j++) {
                int next = i + j;
                if (next >= M)
                    next -= M;

                if (dp_layer[j] < INF && dp2[next] > dp[i] + dp_layer[j]) {
                    dp2[ next ] = dp[i] + dp_layer[j];
                    zmienione2.insert(next);
                }
            }
        }
        zmienione1 = zmienione2;
        dp = dp2;
    }

    res[0] = 0;

    for (int i : res) {
        cout << (i == INF ? -1 : i) << "\n";
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
//    freopen("../d/1.in","r",stdin);
//    freopen("../wzo.out","w",stdout);

//    cin >> t;

    for (int i = 1; i <= t; i++) {
        solve(i);
    }

    return 0;
}
/*
3 2 6
1 2 1
2 2 2
1 1 5

 */