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
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define REP(i, n) for(int i = 0; i < (n); ++i)

template<class T> int size(T && a) {
	return (int)(a.size());
}
ostream& operator << (ostream &os, string str) {
    for(char c : str) os << c;
    return os;
}
template <class A, class B> ostream& operator << (ostream &os, const pair<A, B> &p) {
	return os << '(' << p.first << "," << p.second << ')';
}
template <class T> auto operator << (ostream &os, T &&x) -> decltype(x.begin(), os) {
	os << '{';
	for(auto it = x.begin(); it != x.end(); ++it)
		os << *it << (it == prev(x.end()) ? "" : " ");
	return os << '}';
}
template <class T> ostream& operator << (ostream &os, vector<vector<T>> vec) {
    for(auto x : vec)
    	os << "\n  " << x;
    return os;
}
void dump() {}
template <class T, class... Args> void dump(T &&x, Args... args) {
    cerr << x << "; ";
    dump(args...);
}
#ifdef DEBUG
# define debug(x...) cerr << "[" #x "]: ", dump(x), cerr << '\n'
#else 
# define debug(...) 0
#endif

//--------------------------------------------------

const long long INF = (long long)(1e18);

vector<long long> get_super_jellys(int m, 
							 const vector<vector<pair<int, int>>> &groups) {

	vector<long long> prev_dp(m, INF), dp(m, INF);
	dp[0] = 0;

	for (const auto &group : groups) {
		swap(prev_dp, dp);
		dp = vector<long long>(m, INF);
		

		for (const auto &[weight, price] : group) {
			REP (r, m) {
				dp[r] = min(dp[r], prev_dp[(m + r - weight) % m] + price);
			}
		}
	}

	return dp;
}

vector<long long> knapsack(int m, const vector<long long> &items) {
	vector<long long> dp(m, INF), prev_dp(m, INF);
	dp[0] = prev_dp[0] = 0;

	FOR (weight, 1, m - 1) {
		long long price = items[weight];
		if (price == INF) continue;

		REP (r, m) 
			dp[r] = min(dp[r], prev_dp[(m + r - weight) % m] + price);
		debug(dp);

		vector<bool> visited(m, false);
		REP (r, m) {
			if (visited[r]) continue;

			int start = r;
			visited[start] = true;
			for (int i = (start + weight) % m; i != start; i = (i + weight) % m) {
				visited[i] = true;
				if (dp[i] < dp[start])
					start = i;
			}

			long long transition = dp[start] + price;
			for (int i = (start + weight) % m; i != start; i = (i + weight) % m) {
				dp[i] = min(dp[i], transition);
				transition = dp[i] + price;
			}
			debug(dp);
		}

		debug(weight, price, dp);
		prev_dp = dp;
	}

	return dp;
}

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

	int n, k, m;
	cin >> n >> k >> m;

	vector<vector<pair<int, int>>> colors(k);
	REP (i, n) {
		int color, weight, price;
		cin >> color >> weight >> price;
		--color;

		colors[color].emplace_back(weight, price);
	}

	vector<long long> super_jellys = get_super_jellys(m, colors);
	debug(super_jellys);
	vector<long long> answer = knapsack(m, super_jellys);
	REP (i, m) cout << (answer[i] == INF ? -1 : answer[i]) << '\n';
}