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
#include "bits/stdc++.h"
 
using namespace std;

template<typename _T> void _debug(const char *s, _T x){ cerr << s << " = " << x << "\n";}
template<typename _T, typename... R> void _debug(const char *s, _T x, R... r){ while(*s != ',') cerr << *s++; cerr << " = " << x << ", "; _debug(s + 1, r...);}
 
#define debug(...)  _debug(#__VA_ARGS__,  __VA_ARGS__)
 
#define sz(s)   int32_t(s.size())
#define all(x)  begin(x), end(x)
#define getuniqe(x) x.erase(unique(all(x)), end(x))
#define cena first
#define waga second
 
using ll = long long;
using ld = long double;

#define int ll

const int MAXX = 7e3 + 5, INF = 1e18;
// const int MAXX = 1e2 + 5, INF = 1e18;

int n, k, m;

vector<pair<int, int>> kolor[MAXX];

int dp1[MAXX][MAXX];

int dp[MAXX];

int mod(int r) {
    if (r < 0) r += m;
    if (r >= m) r -= m;
    return r;
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k >> m;
    for (int i = 1; i <= n; i++) {
        int ki, mi, ci; cin >> ki >> mi >> ci;
        kolor[ki].push_back({ci, mi});
    }
    fill(begin(dp1[0]), end(dp1[0]), INF);
    dp1[0][0] = 0;
    for (int i = 1; i <= k; i++) {
        fill(begin(dp1[i]), end(dp1[i]), INF);
        for (int r = 0; r < m; r++) {
            for (pair<int, int> z: kolor[i]) {
                int last_r = mod(r - z.waga);
                dp1[i][r] = min(dp1[i][r], dp1[i - 1][last_r] + z.cena);
            }
        }        
    }
    vector<pair<int, int>> paczki;
    for (int r = 0; r < m; r++) {
        if (dp1[k][r] < INF) paczki.push_back({dp1[k][r], r});
    }
    fill(begin(dp), end(dp), INF);
    dp[0] = 0;
    set<pair<int, int>> q; q.insert({0, 0});
    while (!q.empty()) {
        pair<int, int> t = *(begin(q)); q.erase(begin(q));
        int cen = -t.first;
        int rem = t.second;
        if (cen != dp[rem]) continue;
        for (pair<int, int> p: paczki) {
            int new_rem = mod(rem + p.waga);
            int new_cen = cen + p.cena;
            if (new_cen < dp[new_rem]) {
                dp[new_rem] = new_cen;
                q.insert({-new_cen, new_rem});
            }
        }
    }
    for (int r = 0; r < m; r++) {
        if (dp[r] >= INF) cout << "-1\n";
        else cout << dp[r] << "\n";
    }

}