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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll oldCosts[7000];
ll newCosts[7000];

typedef pair<int, pair<int, ll>> zel;
zel zelki[7001];

int n, k, m;

priority_queue<pair<ll, int>> pq;

int managed_colors = 0;

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

    cin >> n >> k >> m;
    fill(newCosts + 1, newCosts + m, -1);
    for(int i = 1; i <= n; i++){
        cin >> zelki[i].first >> zelki[i].second.first >> zelki[i].second.second;
    }

    sort(zelki + 1, zelki + n + 1);

    for(int i = 1; i <= n; ++i){
        if(zelki[i].first > k) break;

        if(zelki[i].first != zelki[i - 1].first){
            for(int j = 0; j < m; ++j){
                oldCosts[j] = newCosts[j];
                newCosts[j] = -1;
            }
            managed_colors++;
        }
        for(int j = 0; j < m; ++j){
            if(oldCosts[j] == -1) continue;

            int newJ = (j + zelki[i].second.first) % m;

            if(newCosts[newJ] == -1){
                newCosts[newJ] = oldCosts[j] + zelki[i].second.second;
            } else {
                newCosts[newJ] = min(newCosts[newJ], oldCosts[j] + zelki[i].second.second);
            }
        }
    }

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

    newCosts[0] = 0;

    // for(int i = 0; i < m; ++i){
    //     cout << "newCosts[" << i << "] = " << newCosts[i] << "\n";
    // }

    for(int i = 0; i < m; ++i){
        if(newCosts[i] != -1){
            pq.push({-newCosts[i], i});
        }
    }

    while(!pq.empty()){
        auto [cost, mod] = pq.top();
        pq.pop();
        cost = -cost;
        
        if(newCosts[mod] != cost) continue;

        // cout << "mod = " << mod << " cost = " << cost << "\n";

        for(int i = 1; i < m; ++i){
            if(newCosts[i] == -1) continue;
            int newMod = (mod + i) % m;
            if(newCosts[newMod] == -1){
                newCosts[newMod] = cost + newCosts[i];
                pq.push({-newCosts[newMod], newMod});
            }
            else if(newCosts[newMod] > cost + newCosts[i]){
                newCosts[newMod] = cost + newCosts[i];
                pq.push({-newCosts[newMod], newMod});
            }
        }
    }

    for(int i = 0; i < m; ++i){
        cout << newCosts[i] << "\n";
    }
}