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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <bits/stdc++.h>

#define FOR(i, s, e) for (int i = (s); i <= (e); i++)
#define FORD(i, s, e) for (int i = (s); i >= (e); i--)
#define ALL(k) (k).begin(), (k).end()
#define e1 first
#define e2 second
#define mp make_pair

using namespace std;
using LL = long long;
using LD = long double;
using PII = pair<int, int>;
const LL INF = 1000111000LL * 1000111000LL;
const int MAXN = 7111;

class Jelly
{
public:
    int colour;
    int mass;
    LL price;
    bool operator<(Jelly const &jelly)
    {
        if (price == jelly.price)
        {
            return mass < jelly.mass;
        }
        return price < jelly.price;
    }
};

vector<Jelly> jellies[MAXN];

LL dp[MAXN];

LL res[MAXN];

// price x mass
vector<pair<LL,int>> deltas[MAXN];

LL dp_delta[2][MAXN];


int main()
{
    int n, k, m;
    scanf("%d%d%d", &n, &k, &m);

    int gcd_for_mass = m;

    FOR(i, 1, n)
    {
        Jelly jelly;
        scanf("%d%d%lld", &jelly.colour, &jelly.mass, &jelly.price);
        jellies[jelly.colour].push_back(jelly);
    }
    bool base_set_exists = true;
    LL base_set_mass = 0;
    LL base_set_price = 0;
    FOR(i, 1, k)
    {
        if (jellies[i].empty())
        {
            FOR(i, 1, m - 1)
            {
                res[i] = -1;
            }
            base_set_exists = false;
            break;
        }
        sort(ALL(jellies[i]));
        base_set_price += jellies[i][0].price;
        base_set_mass = (base_set_mass + jellies[i][0].mass) % m;
        // printf("Colour %d: first - price %2lld mass %2d; base set price %2lld mass %2d\n", i, jellies[i][0].price, jellies[i][0].mass, base_set_price, base_set_mass);
        FOR (j, 1, jellies[i].size()-1)
        {
            int mass_delta = (m + jellies[i][j].mass - jellies[i][0].mass) % m;
            LL price_delta = jellies[i][j].price - jellies[i][0].price;
            deltas[i].emplace_back(price_delta, mass_delta);
            // printf("\tDelta price %lld mass %d\n", price_delta, mass_delta);
        }
    }
    if (!base_set_exists){
        printf("0\n");
        FOR(i,1,m-1){
            printf("-1\n");
        }
        return 0;
    }
    FOR(i, 0, m - 1)
    {
        if (i % gcd_for_mass != 0)
        {
            res[i] = -1;
        }
        else{
            res[i] = INF;
        }
    }
    res[0] = 0;
    dp_delta[0][0] = 0;
    FOR(i,1,m){
        dp_delta[0][i] = INF;
    }
    int current_dp_idx = 1;
    int last_dp_idx = 0;
    FOR(full_count, 1, m-1){
        LL full_price = base_set_price * full_count;
        LL full_mass = (base_set_mass * full_count) % m;
        // printf("Count %d full price %2lld mass %2d\n", full_count, full_price, full_mass);
        if (full_price < res[full_mass]){
            res[full_mass] = full_price;
        }
        FOR(j,0,m-1){
            dp_delta[current_dp_idx][j] = dp_delta[last_dp_idx][j];
        }
        FOR(col, 1, k){
            if (deltas[col].empty()){
                continue;
            }
            for(auto &it : deltas[col]){
                LL price_delta = it.e1;
                int mass_delta = it.e2;
                int next = mass_delta;
                FOR(i,0,m-1){
                    if (dp_delta[last_dp_idx][i] + price_delta < dp_delta[current_dp_idx][next]){
                        dp_delta[current_dp_idx][next] = dp_delta[last_dp_idx][i] + price_delta;
                    }
                    next++;
                    if (next >= m) {
                        next -= m;
                    }
                }
            }
            swap(current_dp_idx, last_dp_idx);
            memcpy(dp_delta[current_dp_idx], dp_delta[last_dp_idx], m * sizeof(LL));
            // FOR(i,0,m-1){
            //     dp_delta[current_dp_idx][i] = dp_delta[last_dp_idx][i];
            // }
        }
        FOR(i,0,m-1){
            LL price = full_price + dp_delta[current_dp_idx][i];
            int mass = (full_mass + i >= m) ? full_mass+i-m : full_mass + i;
            if (res[mass] == -1 || price < res[mass]){
                res[mass] = price;
            }
        }
    }
    FOR(i,0,m-1){
        printf("%lld\n", res[i]);
    }
}