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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PI;
typedef long long LL;
typedef double D;
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define R(I,N) for(int I=0;I<N;I++)
#define F(I,A,B) for(int I=A;I<B;I++)
#define FD(I,N) for(int I=N-1;I>=0;I--)
#define make(A) scanf("%d",&A)
#define make2(A,B) scanf("%d%d",&A,&B)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define db if(1)printf
template<typename C> void MA(C& a,C b){if(a<b)a=b;}
template<typename C> void MI(C& a,C b){if(a>b)a=b;}
#define MAX 1000100
int n,m;
int inf = 2e9;
vector<pair<int,PI> > d[MAX];
set<int> ak;
int il[MAX];
vector<pair<int,PI> > z;
void pob(){
  make2(n,m);m=0;
  map<int,int> mapa;
  R(i,n){
    int a,b,sk,k;
    make2(a,b);
    make(sk);
    auto it = mapa.find(sk);
    if(it == mapa.end()){
      k = m;
      mapa[sk] = m++;
    }else
      k = it->SE;
    d[k].PB({b,MP(a,i)});
    z.PB({a,MP(b,k)});
  }
  sort(ALL(z));
}
int nn[MAX];
vector<vector<PI>> dp;
void rob_drzewko(int i){
  sort(ALL(d[i]));
  nn[i] = 1;while(nn[i] < SZ(d[i]))nn[i]*=2;
  vector<PI> dp(nn[i]*2,MP(0,0));
  R(j,nn[i]){
    if(j < SZ(d[i]))
      dp[j+nn[i]].FI = d[i][j].FI - j;
    else
      dp[j+nn[i]].FI = inf;
  }
  FD(j,nn[i])
    dp[j].FI = min(dp[j*2].FI,dp[j*2+1].FI);
  ::dp.PB(dp);
}
void usun_z_drzewka(vector<PI>& dp,int kol,int id){
  id += nn[kol];
  dp[id] = {inf,0};
  while(id > 1){
    if((id&1) == 0){
      dp[id+1].FI++;
      dp[id+1].SE++;
    }
    id/=2;
    dp[id].FI = min(dp[id*2].FI,dp[id*2+1].FI) + dp[id].SE;
  }
}
int kiedy = inf;
multiset<int> se[MAX];
int wyn[MAX];
int wynik;
void zajmij(int kol,int kon,int t){
  auto x = lower_bound(ALL(d[kol]),MP(kon,MP(-1,-1)));
  wyn[x->SE.SE] = t;
  x->SE = {-2,-2};
  int id = x - d[kol].begin();
  usun_z_drzewka(dp[kol],kol,id);
}
main(){
  pob();
  
  R(i,m)rob_drzewko(i);
  int t = -1;
  int i = 0;
  while(ak.size() != 0 || i != z.size()){
    if(t > kiedy){
      puts("NIE");
      return 0;
    }
    if(z.size() != i && z[i].FI <= kiedy){
      t = z[i].FI;
      while(t == z[i].FI){
        int kol = z[i].SE.SE; 
        il[kol]++;
        if(il[kol] == 1){
          ak.insert(kol);
          MI(kiedy,dp[kol][1].FI);
        }
        se[kol].insert(z[i].SE.FI);
        i++;
      }
    }else{
      t = kiedy;
      kiedy = inf;
      wynik++;
      vector<int> dous;
      for(int kol:ak){
        il[kol]--;
        auto xxx = se[kol].begin();
        int kon = *xxx;
        se[kol].erase(xxx);
        zajmij(kol,kon,t);
        if(il[kol] == 0)
          dous.PB(kol);
        else
          MI(kiedy,dp[kol][1].FI);
      }
      for(int kol:dous)
        ak.erase(kol);
    }
  }
  printf("%d\n",wynik);
  R(i,n)printf("%d\n",wyn[i]);
}