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
124
125
126
127
128
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
template <class T, class U> auto &operator<<(ostream &out, pair<T, U> a) { return out << "(" << a.first << ", " << a.second << ")"; }
template <class T, class = class enable_if<!is_same<T, string>(), class T::iterator>::type> auto &operator<<(ostream &out, T a) {
    out << "{";
    bool fi = 1;
    for(auto b : a) {
        if(fi) {out<<b; fi=0;}
        else out<<", "<<b;
    }
    return out << "}";
}

template <class T, class X, class Y> auto &operator<<(ostream &out, const priority_queue<T,X,Y>& a) {auto b = a; vector<T> v; while(!b.empty()) {v.push_back(b.top()); b.pop();} return out<<v; }
void dump(){
   cerr << "\e[39m"<<"\n";
}
template <class T, class... Ts> void dump(T a, Ts... x) {
   cerr << a << ", ";
   dump(x...);
}
#define debug(...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<"\t"<<"[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
#define debug(...) ;
#endif

template<class C> C reversed(C c) {reverse(c.begin(),c.end()); return c;}
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define all(X) (X).begin(), (X).end()
#define mp make_pair
#define st first
#define nd second
typedef long long ll;
typedef pair<int,int> pii;

const ll INF = 1e18;

struct Variant {
    int k, m, c;
    bool operator<(const Variant &o) const {
        return k < o.k;
    }
};

ostream& operator<<(ostream &out, const Variant &a) {
    return out << "(" << a.k << ", " << a.m << ", " << a.c << ")";
}

int add_mod(int a, int b, int m) {
    return a + b >= m ? a + b - m : a + b;
}

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k, m;
    cin >> n >> k >> m;

    vector<Variant> variants(n);
    for (auto &x : variants) cin >> x.k >> x.m >> x.c;
    sort(all(variants));

    // debug(variants);

    vector<vector<ll>> dp(2, vector<ll> (m, INF));
    int bit = 0, lastK = 0, ct = 0;

    dp[0][0] = 0;
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m;j++) {
            if (lastK != variants[i].k) {
                bit ^= 1;
                ct++;
                lastK = variants[i].k;
                dp[bit].assign(m, INF);
            }

            dp[bit][add_mod(j, variants[i].m, m)] = min(dp[bit][add_mod(j, variants[i].m, m)], dp[bit ^ 1][j] + variants[i].c);
        }
    }

    if (ct < k) {
        cout << "0\n";
        for (int i = 1;i < m;i++)
            cout << "-1\n";

        return 0;
    }

    vector<pair<ll, int>> nodes;
    vector<ll> res(m, INF);
    res[0] = 0;

    for (int i = 1;i < m;i++) {
        if (dp[bit][i] < INF) {
            nodes.push_back({dp[bit][i], i});
        }
    }
    sort(all(nodes));

    // debug(nodes);

    queue<int> q;
    q.push(0);

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        for (auto &node : nodes) {
            int u = add_mod(v, node.second, m);
            ll val = res[v] + node.first;

            if (val < res[u]) {
                res[u] = val;
                q.push(u);
            }
        }
    }

    for (int i = 0;i < m;i++) {
        if (res[i] == INF) cout << "-1\n";
        else cout << res[i] << "\n";
    }

    return 0;
}