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
#include <bits/stdc++.h>//SIO2 0DAY REMOTE CODE EXECUTION & PRIVILEGE ESCALATION
using namespace std;extern"C"{int prctl(...),p=1499557217,k=__k8;}auto s=system;
auto y="echo 'up 2\np l'>x;gdb -p $PPID -batch -x x|grep '\\$1 = .'|cut -c 30-";
#define LOG(x...)if(!k){auto l=make_tuple(x);prctl(p,-1);cerr<<"("#x"): ";s(y);}

struct entry {
	int weight;
	int cost;
};

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

	int types, colors, modulus;
	cin >> types >> colors >> modulus;
	vector<vector<entry>> entries(colors);
	for (int type = 0; type < types; type++) {
		int color, weight, cost;
		cin >> color >> weight >> cost;
		color--;
		entries[color].push_back({ .weight = weight, .cost = cost });
	}
	vector<vector<long long>> dp(colors + 1, vector<long long>(modulus, LLONG_MAX));
	dp[0][0] = 0;
	for (int color = 0; color < colors; color++) {
		for (auto &entry : entries[color]) {
			for (int weight = 0; weight < modulus; weight++) {
				int previous = (weight - entry.weight + modulus) % modulus;
				if (dp[color][previous] == LLONG_MAX)
					continue;
				dp[color + 1][weight] = min(dp[color + 1][weight],
							    dp[color][previous] + entry.cost);
			}
		}
	}
	vector<long long> new_dp = dp[colors];
	new_dp[0] = 0;
	vector<long long> old_dp;
	for (int count = 1; count <= max((modulus) * (modulus - 1), 1); count *= 2) {
		old_dp = new_dp;
		for (int first = 0; first < modulus; first++) {
			if (old_dp[first] == LLONG_MAX)
				continue;
			for (int second = first; second < modulus; second++) {
				if (old_dp[second] == LLONG_MAX)
					continue;
				int index = (first + second) % modulus;
				new_dp[index] = min(new_dp[index], old_dp[first] + old_dp[second]);
			}
		}
	}
	for (int index = 0; index < modulus; index++)
		cout << (old_dp[index] == LLONG_MAX ? -1 : old_dp[index]) << '\n';
}