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

using namespace std;

typedef long long ll;

unordered_set<int> cls;
vector<pair<ll, ll>> tps[7070];
ll res[7070];
vector<ll> not_inf;
int visited[7070];

const ll inf = (ll)1<<61;

ll costs[7070][2];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll n, k, m;
    cin >> n >> k >> m;

    for(int i = 0; i < n; i++) {
        int ki;
        ll mi, ci;
        cin >> ki >> mi >> ci;

        tps[ki].push_back({mi, ci});
        cls.insert(ki);
    }

    if(cls.size() < k) {
        cout << 0 << "\n";
        for(int i = 1; i < m; i++) {
            cout << -1 << "\n";
        }
        return 0;
    }

    for(int i = 0; i < m; i++) {
        costs[i][0] = inf;
        costs[i][1] = inf;
    }
    
    auto it = cls.begin();
    for(auto t: tps[*it]) {
        costs[t.first%m][0] = min(costs[t.first%m][0], t.second);
    }
    it++;

    int idx = 1;
    for(; it != cls.end(); it++) {
        for(auto t: tps[*it]) {
            for(int i = 0; i < m; i++) {
                ll tmp1 = (i + t.first)%m;
                ll tmp2 = costs[i][idx^1] + t.second;
                if(tmp2 < costs[tmp1][idx]) {
                    costs[tmp1][idx] = tmp2;
                }
            }
        }

        for(int i = 0; i < m; i++) {
            costs[i][idx^1] = inf;
        }
        idx ^= 1;
    }
    idx ^= 1;

    for(int i = 0; i < m; i++) {
        if(costs[i][idx] != inf) {
            not_inf.push_back(i);
        }
    }

    for(int i = 1; i < m; i++) {
        res[i] = inf;
    }

    for(auto w: not_inf) {
        for(int i = 0; i < m; i++) {
            if(res[i] == inf) {
                continue;
            }

            ll best_res = res[i];

            for(int ptr = (i + w)%m, prev_ptr = i; visited[ptr] < 1; prev_ptr = ptr, ptr = (ptr + w)%m) {
                visited[ptr]++;
                res[ptr] = min(res[ptr], res[prev_ptr] + costs[w][idx]);
            }

            if(res[i] == best_res) {
                continue;
            }

            for(int ptr = (i + w)%m, prev_ptr = i; visited[ptr] < 2; prev_ptr = ptr, ptr = (ptr + w)%m) {
                visited[ptr]++;
                res[ptr] = min(res[ptr], res[prev_ptr] + costs[w][idx]);
            }
        }

        for(int i = 0; i < m; i++) {
            visited[i] = 0;
        }
    }

    for(int i = 0; i < m; i++) {
        cout << (res[i] != inf ? res[i] : -1LL) << "\n";
    }

    return 0;
}