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<iostream> 
#include<algorithm>
#include<vector>
#include<cmath>
#include<ctime>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	clock_t t0,t;
	t0 = clock();
	int N,K,M;
	cin>>N>>K>>M;
	const int q = 7000;
	long long k[q],m[q],c[q];
	vector< pair<long long, pair<long long, long long> > > v;
	for(int i=0; i<N; ++i) {
		cin>>k[i]>>m[i]>>c[i];
		m[i] = m[i] % M;
		v.push_back(make_pair(k[i], make_pair(m[i], c[i])));
	}
	sort(v.begin(),v.end());
	for(int i=0; i<N; ++i) {
		k[i] = v[i].first;
		m[i] = v[i].second.first;
		c[i] = v[i].second.second;
	}
	bool CZ[q+1];
	for(int i=1; i<=K; ++i) CZ[i] = false;
	for(int i=0; i<N; ++i) {
		CZ[k[i]] = true;
	}
	for(int i=1; i<=K; ++i) if(CZ[i] == false) {
		cout<<0<<endl;
		for(int j=1; j<M; ++j) cout<<"-1"<<endl;
		return 0;
	}
	long long T[q];
	long long tab[q][q];
	for(int i=0; i<M; ++i) T[i] = -1;
	int C = 1;
	for(int i=0; i<N; ++i) {
		int p = 0;
		while(i < N && k[i] == C) {
			if(k[i] == 1) {
				if(T[m[i]] == -1) T[m[i]] = c[i];
				else T[m[i]] = min(T[m[i]], c[i]);
			}
			else {
				for(int j=0; j<M; ++j) tab[p][j] = T[(j - m[i] + M) % M];
				for(int j=0; j<M; ++j) if(tab[p][j] != -1) tab[p][j] += c[i];
			}
			p++;
			i++;
		}
		if(C != 1) {
			for(int j=0; j<M; ++j) {
				long long Min = (long long)1 << 60;
				for(int e=0; e<p; ++e) {
					if(tab[e][j] != -1) Min = min(Min, tab[e][j]);
				}
				if(Min < ((long long)1 << 60)) T[j] = Min;
				else T[j] = -1;
			}
		}
		i--; C++;
	}
	long long B[q];
	for(int i=0; i<15; ++i) {
		for(int j=0; j<M; ++j) B[j] = -1;
		for(int j=0; j<M; ++j) {
			for(int l=0; l<M; ++l) {
				if(T[j] != -1 && T[l] != -1) {
					if(B[(j + l) % M] == -1) B[(j + l) % M] = T[j] + T[l];
					else B[(j + l) % M] = min(B[(j + l) % M], T[j] + T[l]);
				}
			}
		}
		for(int j=0; j<M; ++j) {
			if(T[j] != -1 && B[j] != -1) T[j] = min(T[j],B[j]);
			else if(T[j] == -1) T[j] = B[j];
		}
		t = clock() - t0;
		if(((float)t)/CLOCKS_PER_SEC > 2.5) break;
	}
	cout<<0<<endl;
	for(int i=1; i<M; ++i) cout<<T[i]<<endl;
	
	return 0;
}