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
#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")

#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
#define int ll
using ll = long long;
using ld = long double;  // or double, if TL is tight
using str = string; 
using ii = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;


signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n, k, m;
    cin >> n >> k >> m;
    vector<vector<ii> > Optiuni(k);
    for(int i = 0; i < n; ++i) {
        int k, m, c;
        cin >> k >> m >> c;
        --k;
        Optiuni[k].push_back({m, c});
    }
    vi DP(m, -1), DPnou(m, -1);
    DP[0] = 0;
    auto improve = [&](int p, int v, vi &V) {
        if(V[p] == -1) {
            V[p] = v;
            return;
        }
        V[p] = min(V[p], v);
    };
    for(int i = 0; i < k; ++i) {
        DPnou.assign(m, -1);

        for(auto [masa, c] : Optiuni[i]) {
            for(int j = 0; j < m; ++j) {
                if(DP[j] != -1)
                    improve((j + masa) % m, DP[j] + c, DPnou);
            }
        }

        DP = DPnou;
    }

    vector<ii> RealOpt;
    for(int i = 1; i < m; ++i) {
        if(DP[i] != -1) {
            for(int j = 0; (1 << j) <= m; ++j) {
                RealOpt.push_back({(1 << j) * i % m, DP[i] * (1 << j)});
            }
        }
    }

    vi DPfin(m, -1);
    DPfin[0] = 0;

    for(auto [v, c] : RealOpt) {
        for(int i = 0; i < m; ++i) {
            if(DPfin[i] == -1) continue;
            improve((i + v) % m, c + DPfin[i], DPfin);
        }
    }
    for(auto it : DPfin) cout << it << "\n";
    return 0;
}