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

using namespace std;
const long long maxn=7009;
long long dp[maxn], dp2[maxn], plecak[maxn];
vector<pair<long long, long long>> zelki[maxn], przedmiot;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, k, m, a, b, c;
    cin >> n >> k >> m;
    for(long long i=1; i<=n; i++) {
        cin >> a >> b >> c;
        zelki[a].push_back({b, c});
    }
    for(long long i=0; i<m; i++) {
        dp[i]=1000'000'000'000'000'000;
        dp2[i]=1000'000'000'000'000'000;
    }
    dp[0]=0;
    long long ile=0;
    for(long long i=1; i<=k; i++) {
        if(zelki[i].size()==0) {
            continue;
        }
        ile++;
        for(auto xd:zelki[i]) {
            for(long long j=0; j<m; j++) {
                dp2[(j+xd.first)%m]=min(dp2[(j+xd.first)%m], dp[j]+xd.second);
            }
        }
        for(long long i=0; i<m; i++) {
            dp[i]=dp2[i];
            dp2[i]=1000'000'000'000'000'000;
        }
    }
    if(ile!=k) {
        cout << 0 << endl;
        for(long long i=2; i<=m; i++) {
            cout << -1 << endl;
        }
        return 0;
	}
	
	
	
    /*for(int i=1; i<m; i++) {
		cout << dp[i] << endl;
	}	
	return 0;*/
    dp[0]=0;
    long long gdzie, koszt;
    dp2[0]=0;
    for(long long i=1; i<m; i++) {
        dp2[i]=min(dp2[i], dp[i]);
        gdzie=i;
        koszt=dp[i];
        for(long long j=1; j<=m; j++) {
            dp2[gdzie]=min(dp2[gdzie], koszt);
            koszt+=dp[i];
            if(koszt>1000'000'000'000'000'000) {
				break;
			}	
            gdzie+=i;
            gdzie%=m;
        }
    }
    for(long long i=1; i<m; i++) {
        plecak[i]=1000'000'000'000'000'000;
        if(dp2[i]<1000'000'000'000'000'000){
			dp2[i]=min(dp2[i], (long long)1000'000'000'000'000'000);
            przedmiot.push_back({i, dp2[i]});

        }
    }
    
    
    
    plecak[0]=0;
    long long waga;
    for(auto prz:przedmiot) {
        waga=prz.first;
        koszt=prz.second;
        for(long long i=0; i<m; i++) {
            plecak[(i+waga)%m]=min(plecak[(i+waga)%m], plecak[i]+koszt);
            min((long long)1000'000'000'000'000'000, plecak[(i+waga)%m]);
        }
    }
    for(long long i=0; i<m; i++){
        if(plecak[i]==1000'000'000'000'000'000){
            cout << -1 << endl;
        }
        else {
            cout << plecak[i] << endl;
        }
    }
}