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
// clang-format off
    #include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define ssize(x) int(x.size())
    template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
    template<typename T,typename = typename enable_if<!is_same<T,string>::value>::type>
    auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
    #ifdef DEBUG
    #define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
    #else
    #define debug(...) {}
    #endif
    // clang-format on
    #define int long long

    bool nie=0;
    int n, m, k, a, b, c, sumakosztu, sumawag;
    vector<pair<int, int>> kolory[10000];
    vector<pair<int, int>> zmiany[10000];
    vector<int> dp, pom, zera, odp;

    int32_t main()
    {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        cin >> n >> k >> m;
        for (int i = 0; i < n; i++)
        {
            cin >> a >> b >> c;
            kolory[a].push_back({b % m, c});
        }
        for (int i = 1; i <= k; i++)
        {
            if (kolory[i].size() > 0)
            {
                sort(kolory[i].begin(), kolory[i].end());
                sumakosztu += kolory[i][0].second;
                sumawag += kolory[i][0].first;
                for (int j = 1; j < (int)kolory[i].size(); j++)
                {
                    zmiany[i].push_back({kolory[i][j].first - kolory[i][0].first, kolory[i][j].second - kolory[i][0].second});
                }
            }
            else
            {
                nie =1;
                sumakosztu += 1000000000000000000;
            }
        }
        //cout << zmiany << endl;
        if(nie){
            cout << 0 << endl;
            for(int i=1;i<m;i++)cout << -1 << endl;

            return 0;
        }
        for (int i = 0; i < m; i++)
        {
            dp.push_back(1000000000000000000);
            pom.push_back(1000000000000000000);
            zera.push_back(1000000000000000000);
            odp.push_back(1000000000000000000);
        }
        odp[0] = 0;
        sumawag %= m;
        dp[sumawag] = min(dp[sumawag], sumakosztu);
        //cout << zmiany << endl;
        for (auto i2=1;i2<=k;i2++)
        {
            for(auto i:zmiany[i2]){
            for(int o=0;o<m;o++)if(dp[o]!=1000000000000000000)pom[(o + i.first) % m] = min(pom[(o + i.first) % m], dp[o] + i.second);
            }
        for (int i = 0; i < m; i++)
        {
            dp[i] = min(pom[i], dp[i]);
        
        }}
        dp[0]=0;
         //cout << dp << endl;

        for (int it = 0; (1 << it) <= 16 * m; it++)
        {
            pom = zera;
            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    a = (i + j);
                    if (a >= m)
                        a -= m;
                    pom[a] = min(pom[a], dp[i] + dp[j]);
                }
            }
                //cout << dp << endl;
            for (int i = 0; i < m; i++)
                dp[i] = min(dp[i], pom[i]);
        }

        for (int i : dp)
        {
            if (i == 1000000000000000000)
                cout << -1 << endl;
            else
                cout << i << endl;
        }
        return 0;
    }