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

#define ll long long
#define fors(u, n, s) for(ll u = (s); u < (n); u++)
#define foru(u, n) fors(u, n, 0)
#define vec vector
#define pb push_back
#define f first
#define s second
#define ir(a, b, x) (((a) <= (x)) && ((x) <= (b)))
#define pint pair<int, int>

using namespace std;

const int N = 8e3;
int n, k, m;

vec<pair<int, ll>> gummies[N]; // {weight, cost}

ll cost_dp[N];
ll cost_dp_saved[N];

bool visited[N];

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

	//n = 7000; k=3500; m=7000;
	cin >> n >> k >> m;

	foru(_i, n){
		int ki, mi, wi; 
		cin >> ki >> mi >> wi; ki--;
		//ki = _i%k; mi = rand()%m; wi=rand(); 
		gummies[ki].pb({mi, wi});
	}

	foru(i, k) { 
		if(gummies[i].size()==0){
			cout << 0;
			foru(_i, m-1) cout << "\n-1";
			return 0;
		}
	}

	foru(i, m) cost_dp[i] = LLONG_MAX/2;
	cost_dp[0] = 0;

	foru(k_, k){
		foru(i, m) cost_dp_saved[i]=cost_dp[i];
		foru(i, m) cost_dp[i] = LLONG_MAX/2;
		for(auto g : gummies[k_]) {
			foru(i, m) {
				int next = i-g.f+m;
				if (next >= m) next -= m;
				cost_dp[i] = min(cost_dp[i], cost_dp_saved[next]+g.s);
			}
		}
	}

	foru(i, m) cost_dp_saved[i] = cost_dp[i];
	foru(i, m ) cost_dp[i] = LLONG_MAX/2;
	cost_dp[0]=0;

	fors(i, m, 1) {
		if(cost_dp_saved[i] == LLONG_MAX/2) continue;
		ll cst = cost_dp_saved[i];
		foru(j, m) visited[j]=false;
		foru(j, m) {
			if (visited[j]) continue;
			int pos = j;
			int loop = 0;
			while(loop < 2) {
				int pos_ = pos+i;
				if(pos_ >= m) pos_-=m;
				cost_dp[pos_] = min(cost_dp[pos_], cost_dp[pos] + cst);
				pos = pos_;
				visited[pos]=true;
				if (pos == j) loop ++;
			}
		}
	}

	foru(i, m){
		if(cost_dp[i] == LLONG_MAX/2) cout << "-1\n";
		else cout << cost_dp[i] << "\n";
	}

	return 0;
}