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

using namespace std;

#ifdef D
#define DEBUG(x)        \
    do {                \
        x               \
        cout.flush();   \
    } while (0)
#else
#define DEBUG(x)
#endif

using ll = long long;
using pii = pair<int, int>;

const int NMAX = 7007;

int n, k, m, cl, ms, pr;
ll res[NMAX], price_k[NMAX], price_h[NMAX];
vector<pii> mp[NMAX];
vector<pair<int, ll>> p_idx_pk;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k >> m;

    for (int i = 0; i < n; i++) {
        cin >> cl >> ms >> pr;
        mp[cl].emplace_back(ms, pr);
    }

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

    for (int i = 1; i <= k; i++) {
        for (auto &[ms, prc] : mp[i]) {
            for (int j = 0; j < m; j++) {
                int rest = (j + ms) % m;
                if (price_k[j] >= 0 && (price_h[rest] > price_k[j] + prc || price_h[rest] < 0)) {
                    price_h[rest] = price_k[j] + prc;
                }
            }
        }

        for (int j = 0; j < m; j++) {
            price_k[j] = price_h[j];
            price_h[j] = -1;
        }
    }

    for (int i = 1; i < m; i++) {
        if (price_k[i] <= 0) {
            continue;
        }

        int tmp = i;
        ll x = price_k[i];

        do {
            x += price_k[i];
            tmp += i;
            tmp %= m;
            if (price_k[tmp] < 0 || price_k[tmp] > x) {
                price_k[tmp] = x;
            }
        } while (tmp != i);
    }

    for (int i = 0; i < m; i++) {
        if (price_k[i] > 0) {
            p_idx_pk.emplace_back(i, price_k[i]);
        }
    }

    for (auto &[idx, pk] : p_idx_pk) {
        for (int i = 0; i < m; i++) {
            if (res[i] >= 0) {
                int rest = (i + idx) % m;
                res[rest] = res[rest] < 0 ? res[i] + pk : min(res[rest], res[i] + pk);
            }
        }
    }

    for (int i = 0; i < m; i++) {
        cout << res[i] << '\n';
    }

    return 0;
}