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
#include <bits/stdc++.h>
#define LL_INF 10000000000000007

typedef long long ll;
typedef std::string str;
typedef std::pair<ll, ll> llPair;

template <typename T>
using vec = std::vector<T>;

using namespace std;

int n, k, M;
struct Cuk {
  int k;
  int m;
  ll c;
};

// [kolor][reszta]
vec<vec<ll>> dp;
vec<Cuk> cuks;

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

  cin>>n>>k>>M;

  dp = vec<vec<ll>>(k + 1, vec<ll>(M, -1));
  dp[0][0] = 0;

  for(int i = 0; i < n; i++) {
    int k, m;
    ll c;
    cin>>k>>m>>c;
    cuks.push_back({k, m, c});
  }
  sort(cuks.begin(), cuks.end(), [](Cuk c1, Cuk c2) { return c1.k < c2.k; });

  // najmniejsze ciagi po jeden
  for(auto [k, m, c] : cuks) {
    for(int i = 0; i < M; i++) {
      if(dp[k - 1][i] == -1) continue;
      int nm = (m + i) % M;
      if(dp[k][nm] == -1) dp[k][nm] = dp[k - 1][i] + c;
      else dp[k][nm] = min(dp[k - 1][i] + c, dp[k][nm]);
    }
  }

  vec<ll> tab(M);
  for(int i = 0; i < M; i++) tab[i] = dp[k][i];
  tab[0] = 0;

  // wielokrotnosci
  for(int i = 1; i < M; i++) {
    if(tab[i] == -1) continue;
    ll v = tab[i];
    ll mult = 2;
    for(int j = 0; j < M; j++) {
      int ind = (i * mult) % M;
      ll cur_val = v * mult;
      if(tab[ind] == -1) tab[ind] = cur_val;
      else tab[ind] = min(tab[ind], cur_val);
      mult++;
    }
  }
  
  // sumowanie
  // {weight, v}
  vec<pair<int,ll>> els;
  for(int i = 0; i < M; i++) if(tab[i] != -1) els.push_back({i, tab[i]});
  // [kolejne elementy][reszta z dzielenia]
  dp = vec<vec<ll>>(els.size(), vec<ll>(M, -1));
  dp[0][0] = 0;
  for(int i = 1; i < els.size(); i++) {
    auto [m, v] = els[i];
    for(int j = 0; j < M; j++) {
      if(dp[i - 1][j] == -1) continue;
      if(dp[i][j] == -1) dp[i][j] = dp[i - 1][j];
      else dp[i][j] = min(dp[i - 1][j], dp[i][j]);
      int nm = (m + j) % M;
      if(dp[i][nm] == -1) dp[i][nm] = v + dp[i - 1][j];
      else dp[i][nm] = min(dp[i][nm], v + dp[i - 1][j]);
    }
  }

  for(int i = 0; i < M; i++) {
    cout<<dp[els.size() - 1][i]<<"\n";
  }

  cout.flush();
}