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

#define ll long long
#define rowsToCalc n

constexpr int maxn = 7007;
constexpr ll inf = ~(1ll << 63);
int n, k, m;
std::vector<ll> dp[maxn]; // dp[i][j] = minimalny koszt, aby kupić i cukierków każdego koloru, o masie === j (mod m)
std::vector<ll> tmp;
std::vector<std::pair<int, int>> zelki[maxn]; // zelki w danym kolorze (format {masa, koszt})

constexpr int bufSize = (3 * 6 + 6 + 6 + 12) * maxn + 2137;
char buffer[bufSize];
int bufIndex, realBufSize;
void init_buffer() {
    realBufSize = fread_unlocked(buffer, sizeof(char), bufSize, stdin);
}
void getInt(int& x) {
    while((buffer[bufIndex] < '0' || buffer[bufIndex] > '9') && bufIndex < realBufSize)
        bufIndex++;
    x = 0;
    while(('0' <= buffer[bufIndex] && buffer[bufIndex] <= '9') && bufIndex < realBufSize) {
        x = x * 10 + (buffer[bufIndex] - '0');
        bufIndex++;
    }
}

void input() {
    init_buffer();
//    scanf("%d%d%d", &n, &k, &m);
    getInt(n); getInt(k); getInt(m);
    int ki, mi, ci;
    for(int i = 0; i < n; i++) {
//        scanf("%d%d%d", &ki, &mi, &ci);
        getInt(ki); getInt(mi); getInt(ci);
        zelki[ki].push_back({mi, ci});
    }
}

bool chk() {
    for(int i = 1; i <= k; i++)
        if(zelki[i].empty())
            return false;
    return true;
}

void calcDpRow(int i) {
    dp[i].resize(m, inf);
    for(int j = 0; j < m; j++)
        dp[i][j] = inf;
    for(int j = 0; j < m; j++) {
        if(dp[i - 1][j] == inf)
            continue;
        for(const auto& [mass, cost] : zelki[1])
            dp[i][(j + mass) % m] = std::min(dp[i][(j + mass) % m], dp[i - 1][j] + cost);
    }
    for(int kolor = 2; kolor <= k; kolor++) {
        tmp.resize(m);
        for(int j = 0; j < m; j++)
            tmp[j] = inf;
        for(int j = 0; j < m; j++) {
            if(dp[i][j] == inf)
                continue;
            for(const auto& [mass, cost] : zelki[kolor])
                tmp[(j + mass) % m] = std::min(tmp[(j + mass) % m], dp[i][j] + cost);
        }
        std::swap(tmp, dp[i]);
    }
}

void calcDp() {
    dp[0].resize(m, inf);
    dp[0][0] = 0;
    for(int i = 1; i <= rowsToCalc; i++)
        calcDpRow(i);
}

ll answer(int r) {
    ll ans = inf;
    for(int i = 1; i <= rowsToCalc; i++)
        ans = std::min(ans, dp[i][r]);
    return ans;
}

int main() {
    input();
    printf("0\n");
    if(!chk()) {
        for(int i = 1; i < m; i++)
            printf("-1\n");
        return 0;
    }
    calcDp();
    for(int i = 1; i < m; i++) {
        auto ans = answer(i);
        printf("%lld\n", ans == inf ? -1 : ans);
    }
    return 0;
}