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
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define fi first
#define se second
#define pn printf("\n")
#define ssize(x) int(x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define bitcount(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)
#define ctz(x) __builtin_ctz(x)
using namespace std;
typedef __int128 ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
#define vv vector
/*void read(int &a){
		char c = getchar_unlocked(); a = 0;
		while(c<'0' || '9'<c) c = getchar_unlocked();
		while('0'<=c&&c<='9') a = (a<<3)+(a<<1)+c-'0', c = getchar_unlocked();
}*/
int inf = 2e09; ll infll = 1e12; int mod = (1<<23)*119+1;
void out(__int128 a){
		if(!a) return void(putchar_unlocked('0'));
		vv<char> t;
		while(a) t.emplace_back(a%10+'0'), a /= 10;
		while(ssize(t)) putchar_unlocked(t.back()), t.pop_back();
}
void answer(){
		infll *= infll;
		int n, k, m; scanf("%d%d%d", &n, &k, &m);
		vv<vv<pil>> v(k+1);
		for(int i = 0, a, b, c; i < n; ++i) scanf("%d%d%d", &a, &b, &c), v[a].emplace_back(b%m, c);
		vv<ll> dp(m, infll), dpt(m, infll); dp[0] = 0;
		for(int i = 1; i <= k; ++i){
				for(pil u : v[i])
						for(int j = 0; j < m; ++j) dpt[(j+u.fi)%m] = min(dpt[(j+u.fi)%m], dp[j]+u.se);
				dp = dpt, fill(all(dpt), infll);
		}
		//~ for(int i = 0; i < m; ++i) printf("%lld ", dp[i]);
		//~ pn;
		for(int i = 1; i < m; ++i) if(dp[i] != infll)
				for(int j = 2; i*j%m != i; ++j) dp[i*j%m] = min(dp[i*j%m], dp[i]*ll(j));
		
		//~ for(int j = 0; j < m; ++j) printf("%lld ", dp[j]);
		//~ pn;
				
		vv<ll> el = dp; fill(all(dp), infll), dp[0] = 0;
		for(int i = 0; i < m; ++i) if(el[i] != infll){
				for(int j = 0; j < m; ++j) dpt[(j+i)%m] = min(dpt[(j+i)%m], dp[j]+el[i]);
				for(int j = 0; j < m; ++j) dp[j] = min(dp[j], dpt[j]);
				//~ printf("%d\n", i);
				//~ for(int j = 0; j < m; ++j) printf("%lld ", dp[j]);
				//~ pn;
				fill(all(dpt), infll);
		}
		for(int i = 0; i < m; ++i){
				if(dp[i] == infll) printf("-1\n");
				else out(dp[i]), printf("\n");
				//~ printf("%lld\n", dp[i] != infll ? dp[i] : -1ll);
		}
}
signed main(){
		int T = 1;
		//~ scanf("%d", &T);
		//~ ios_base::sync_with_stdio(0); cin.tie(0); //cin >> T;
		for(++T; --T; ) answer();
		return 0;
}