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
// clang-format off
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
#define FOR(i,l,r) for(auto i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<"("<<p.first<<", "<<p.second<<")";}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<"}";}
#ifdef DEBUG
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif
// clang-format on

// Global variables
const int max_price = 1000000000;
const LL INF        = numeric_limits<LL>::max() - max_price - 1;
int nsweets, ncolours, mod;

vector<LL>
get_dp()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> nsweets >> ncolours >> mod;
    vector<tuple<int, int, int>> sweets(nsweets);  // (colour, mass, price)
    for (auto& sw : sweets) cin >> get<0>(sw) >> get<1>(sw) >> get<2>(sw);
    sort(sweets.begin(), sweets.end());

    vector<LL> dp(mod, INF), odp;
    dp[0]           = 0;
    int last_colour = 0;
    vector<bool> colours_used(ncolours);
    for (const auto& sw : sweets) {
        const auto& [colour, mass, price] = sw;
        colours_used[colour - 1]          = true;
        if (last_colour != colour) {
            last_colour = colour;
            swap(dp, odp);
            dp.assign(mod, INF);
        }

        REP (r, mod) {
            int nr = r + mass;
            if (nr >= mod) nr -= mod;
            dp[nr] = min(dp[nr], odp[r] + price);
        }
    }

    // Edge case: some colours unused
    REP (c, ncolours) {
        if (colours_used[c]) continue;
        cout << "0\n";
        FOR (r, 1, mod - 1) cout << "-1\n";
        exit(0);
    }

    debug(dp);
    return dp;
}

int
main()
{
    // Calculate dp: min price for given remainder
    vector<LL> dp(get_dp());
    vector<bool> optimised(mod);
    REP (iteration, mod) {
        // Find the lowest guy that is not optimised
        int opt = -1;
        REP (i, mod) {
            if (optimised[i]) continue;
            if (opt == -1)
                opt = i;
            else if (dp[i] < dp[opt])
                opt = i;
        }
        if (dp[opt] == INF) break;
        debug(opt, dp[opt]);

        REP (r, mod) {
            if (dp[r] == INF) continue;
            int nr = opt + r;
            if (nr >= mod) nr -= mod;
            if (optimised[nr]) continue;
            dp[nr] = min(dp[nr], dp[opt] + dp[r]);
        }

        optimised[opt] = true;
    }
    debug(dp);

    cout << "0\n";
    FOR (r, 1, mod - 1) cout << (dp[r] == INF ? -1 : dp[r]) << "\n";
#ifdef LOCAL
    system("grep VmPeak /proc/$PPID/status >&2");
#endif
    return 0;
}