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
#include <cstdio>
#include <cstdint>
#include <vector>

using namespace std;

int main () {
	int n, k, m;
	scanf("%d %d %d", &n, &k, &m);
	vector<vector<pair<int, int> > > zelki(k, vector<pair<int, int> >());
	for (int i = 0; i < n; ++i) {
		int ki, mi, ci;
		scanf("%d %d %d", &ki, &mi, &ci);
		zelki[ki - 1].push_back(make_pair(mi % m, ci));
	}
	for (int i = 0; i < k; ++i) {
		if (zelki[i].size() > 0) {
			continue;
		}
		printf("0\n");
		for (int j = 1; j < m; ++j) {
			printf("-1\n");
		}
		return 0;
	}
	vector<int64_t> partial(m, -1);
	partial[0] = 0;
	for (int i = 0; i < k; ++i) {
		vector<int64_t> next(m, -1);
		for (int j = 0; j < zelki[i].size(); ++j) {
			int mi = zelki[i][j].first;
			int ci = zelki[i][j].second;
			for (int l = 0; l < m; ++l) {
				if (partial[l] == -1) {
					continue;
				}
				int m2 = (l + mi) % m;
				int64_t c2 = partial[l] + ci;
				if ((next[m2] == -1) || (c2 < next[m2])) {
					next[m2] = c2;
				}
			}
		}
		partial = next;
	}
	partial[0] = 0;
	int max_c = 1;
	while (max_c < m) {
		vector<int64_t> next(m, -1);
		for (int i = 0; i < m; ++i) {
			int64_t pi = partial[i];
			if (pi == -1) {
				continue;
			}
			int idx = (i << 1) % m;
			for (int j = i; j < m; ++j) {
				int64_t pj = partial[j];
				if (pj == -1) {
					++idx;
					if (idx == m) {
						idx = 0;
					}
					continue;
				}
				int64_t part = pi + pj;
				if ((next[idx] == -1) || (part < next[idx])) {
					next[idx] = part;
				}
				++idx;
				if (idx == m) {
					idx = 0;
				}
			}
		}
		max_c <<= 1;
		partial = next;
	}
	for (int i = 0; i < m; ++i) {
		printf("%lld\n", partial[i]);
	}
	return 0;
}