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
#include <vector>
#include <iostream>
#include <numeric>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef unsigned long long ull;

int main() {
    ios_base::sync_with_stdio(false);

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

    vector<vector<pair<ull, ull>>> sweets(k + 1);

    int a;
    ull b, c;
    for (int i = 0; i < n; i++) {
        cin >> a >> b >> c;
        sweets[a].emplace_back(b, c);
    }

    bool all_colors = true;
    for (int i = 1; i <= k; i++) {
        all_colors = all_colors && !sweets[i].empty();
    }

    if (all_colors) {
        unordered_map<ull, ull> compositions;
        compositions[0] = 0;

        for (int i = 1; i <= k; i++) {
            unordered_map<ull, ull> new_compositions;

            for (const auto sweet: sweets[i]) {
                for (const auto &comp: compositions) {
                    auto weight = (comp.first + sweet.first) % m;
                    auto price = comp.second + sweet.second;
                    if (new_compositions.contains(weight)) {
                        new_compositions[weight] = min(new_compositions[weight], price);
                    } else {
                        new_compositions[weight] = price;
                    }
                }
            }

            compositions = new_compositions;
        }

        unordered_map<ull, ull> base(compositions);

        bool found_new = true;
        bool better_found = true;
        while (found_new || better_found) {
            found_new = false;
            better_found = false;
            unordered_map<ull, ull> new_base(base);

            for (auto item: base) {
                for (const auto comp: compositions) {
                    auto weight = (item.first + comp.first) % m;
                    auto price = item.second + comp.second;
                    if (!new_base.contains(weight)) {
                        found_new = true;
                        new_base[weight] = price;
                    } else {
                        if (price < new_base[weight]) {
                            better_found = true;
                            new_base[weight] = min(new_base[weight], price);
                        }
                    }
                }
            }

            base = new_base;
        }

        base[0] = 0;

        for (int i = 0; i < m; i++) {
            if (base.contains(i)) {
                cout << base[i] << endl;
            } else {
                cout << -1 << endl;
            }
        }

    } else {
        cout << 0 << endl;
        for (int i = 1; i < m; i++) {
            cout << -1 << endl;
        }
    }

    return 0;
}