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
#include <bits/stdc++.h>
using namespace std;
inline int64_t millis() {
    return chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now().time_since_epoch()).count();
}

int main() {
    int64_t t0 = millis();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, k, m;
    cin >> n >> k >> m;
    vector<map<int, int>> vv(k + 1);
    vector<vector<pair<int, int>>> v(k);
    for(int i = 0; i < n; i++) {
        int k, m, c;
        cin >> k >> m >> c;
        vv[k][m] = vv[k][m] == 0 ? c : min(c, vv[k][m]);
    }
    bool all = true;
    for(int i = 1; i <= k; ++i)
        if(vv[i].size() == 0) {
            cout << "0\n";
            for(i = 1; i < m; ++i) cout << "-1\n";
            return 0;
        }
    for(int i = 1; i <= k; ++i)
        for(auto&& e : vv[i]) v[i - 1].push_back(e);
    vector<long long> ans(m, LLONG_MAX);
    ans[0] = 0;
    int i = 0;
    // https://stackoverflow.com/a/31169617/6732111
    auto product = [](long long a, vector<pair<int, int>>& b) { return a * b.size(); };
    for(long long k = 1; millis() - t0 < 2850; ++k) {
        vector<pair<int, int>> u(k * v.size());
        long long N = pow(accumulate(v.begin(), v.end(), 1LL, product), k);
        for(long long n = 0; millis() - t0 < 2850 && n < N; ++n) {
            lldiv_t q{n, 0};
            for(long long i = k * v.size() - 1; 0 <= i; --i) {
                q = div(q.quot, v[i / k].size());
                u[i] = v[i / k][q.rem];
            }
            long long ss = 0, cc = 0;
            for(auto&& [k, v] : u) ss += k, cc += v;
            ss %= m;
            ans[ss] = min(ans[ss], cc);
        }
    }
    for(auto&& e : ans) cout << (e == LLONG_MAX ? -1 : e) << '\n';
}