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
#include <bits/stdc++.h>

#define MAX_N  7007
#define mp make_pair

typedef long long ll;

using namespace std;

int n, k, m, color, mass;
ll price;
vector<pair<ll, ll>> 週間[MAX_N];
ll kprice[MAX_N], tprice[MAX_N];
ll res[MAX_N];
vector<pair<int, ll>> qprice;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k >> m;

    for (int i = 0; i < n; i++) {
        cin >> color >> mass >> price;
        週間[color].push_back(mp(mass, price));
    }

    for (int i = 1; i < m; i++) {
        tprice[i] = -1;
        kprice[i] = -1;
        res[i] = -1;
    }
    tprice[0] = -1;

    for (int i = 1; i <= k; i++) {
        for (auto p : 週間[i]) {
            for (int i = 0; i < m; i++) {
                if (kprice[i] >= 0 && (tprice[(i + p.first) % m] < 0 || tprice[(i + p.first) % m] > kprice[i] + p.second)) {
                    tprice[(i + p.first) % m] = kprice[i] + p.second;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            kprice[i] = tprice[i];
            tprice[i] = -1;
        }
    }

    for (int i = 1; i < m; i++) {
        int temp = i;
        ll tp = kprice[i];
        if (tp <= 0) {
            continue;
        }   
        do {
            tp += kprice[i];
            temp += i;
            temp %= m;
            if (kprice[temp] < 0 || kprice[temp] > tp) {
                kprice[temp] = tp;
            }
        } while(temp != i);
    }

    for (int i = 0; i < m; i++) {
        // cout << kprice[i] << " " << tprice[i] << "\n";
        if (kprice[i] > 0) {
            qprice.push_back(mp(i, kprice[i]));
        }
    }

    for (auto q : qprice) {
        for (int i = 0; i < m; i++) {
            if (res[i] >= 0) {
                if (res[(i + q.first) % m] < 0) {
                    res[(i + q.first) % m] = res[i] + q.second;
                } else {
                    res[(i + q.first) % m] = min(res[(i + q.first) % m], res[i] + q.second);
                }
                
            }
        }
    }

    // kaban.push(mp(0, 0));
    // while(!kaban.empty()) {
    //     auto p = kaban.top();
    //     kaban.pop();
    //     if (res[p.second] >= 0 && -p.first >= res[p.second]) {
    //         continue;
    //     }
    //     // cout << p.first << " " << p.second << " ---\n";
    //     res[p.second] = -p.first;
    //     for (auto q : qprice) {
    //         kaban.push(mp(p.first - q.second, (p.second + q.first) % m));
    //     }
    // }
    
    for (int i = 0; i < m; i++) {
        cout << res[i] << "\n";
    }
    return 0;
}