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

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

#define x first
#define y second
#define ir(a, x, b) ((a) <= (x) && (x) <= (b))
#define vec vector
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) (x).begin(), (x).end()

using ll = long long;

const ll INF = ll(1e18);

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N, K, M;
    cin >> N >> K >> M;
    vec<vec<pair<int, ll>>> cs(K);
    rep (i, 0, N) {
        int k; cin >> k; --k;
        int m, c; cin >> m >> c;
        cs[k].push_back({m%M, c});
    }
    debug(cs);
    vec<vec<ll>> dp(K, vec<ll>(M, INF));
    rep (i, 0, cs[0].size()) {
        dp[0][cs[0][i].x] = min(dp[0][cs[0][i].x], cs[0][i].y);
    }
    rep (k, 1, K) {
        for (auto [v, c] : cs[k]) {
            rep (i, 0, M) {
                dp[k][(i+v)%M] = min(c + dp[k-1][i], dp[k][(i+v)%M]);
                debug(dp[k], v);
            }
        }
    }
    debug(dp);
    vec<ll> dp2(M, INF), dp2t(M, INF);
    dp2[0] = 0;
    vec<char> used(M);
    rep (i, 0, M) {
        used.assign(M, 0);
        int v = i;
        ll cost = dp.back()[i];
        while (dp2[v] > cost) {
            rep (m, 0, M) {
                dp2t[(m+v)%M] = min(dp2[(m+v)%M], cost + dp2[m]);
            }
            dp2.swap(dp2t);
            cost *= 2;
            v = (2*v)%M;
        }
        debug(dp2);
    }
    rep (i, 0, M) cout << (dp2[i]>=INF?-1:dp2[i]) << "\n";
    return 0;
}