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
#include <bits/stdc++.h>

using namespace std;



int main(){
ios_base::sync_with_stdio(false);
cin.tie();
cout.tie();
  int n,k,m;cin>>n>>k>>m;
  vector<pair<int,int>>v;
  vector<vector<pair<int,int>>>KV(k+1,v);
  int K[n],M[n],C[n];
  for(int i=0;i<n;i++){
    cin>>K[i]>>M[i]>>C[i];
    KV[K[i]].push_back((pair<int,int>){C[i],M[i]});
  }
  pair<long long,int> S;S.first=0;S.second=0;

  vector<long long>MM(m,-1);
  
  for(int i=1;i<=k;i++){
    if(KV[i].empty()){
      cout<<0<<"\n";
      for(int j=1;j<m;j++)cout<<-1<<"\n";
      return 0;
    }
    sort(KV[i].begin(),KV[i].end());
    S.first+=KV[i][0].first;S.second+=KV[i][0].second;S.second%=m;
  }
  
  if(MM[S.second]==-1 or MM[S.second]>S.first)MM[S.second]=S.first;
  
  for(int i=1;i<=k;i++){
    vector<pair<long long, int>> SS;
    auto IT=KV[i].begin();
    for(auto it=KV[i].begin();it!=KV[i].end();it++){
      long long dc,dm;dc=it->first-IT->first;dm=it->second-IT->second;
      dm=(dm+m)%m;
      for(int j=0;j<m;j++){
        if(MM[j]==-1)continue;
        int J=(j+dm)%m;
        if(MM[J]==-1 or MM[J]>MM[j]+dc)
          SS.push_back((pair<long long,int>){MM[j]+dc,J});
      }
    }
    for(auto it=SS.begin();it!=SS.end();it++){
      int J=it->second;long long c=it->first;
      if(MM[J]==-1 or MM[J]>c)MM[J]=c;
    }
  }
  
  MM[0]=0;
//  for(int i=0;i<m;i++)cout<<MM[i]<<"\n";

  vector<pair<long long,int>>SS;
  for(int i=0;i<m;i++)SS.push_back((pair<long long,int>){MM[i],i});
  
  sort(SS.begin(),SS.end());
  
  for(auto it=SS.begin();it!=SS.end();it++){
    if(it->first==-1)continue;
    for(auto jt=SS.begin();jt!=it+1;jt++){
      if(jt->first==-1)continue;
      int J=it->second+jt->second;J%=m;long long c=it->first+jt->first;
      if(MM[J]==-1 or MM[J]>c)MM[J]=c;
    }
    for(int i=0;i<m;i++)SS[i].first=MM[SS[i].second];
    sort(SS.begin(),SS.end());
  }
//  for(auto it=SS.begin();it!=SS.end();it++)MM[it->second]=it->first;
  
  for(int i=0;i<m;i++)cout<<MM[i]<<"\n";

return 0;
}