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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include<algorithm>
#include<cstdio>
#include<queue>
#include<utility>
#include<vector>

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
using namespace std;

struct reservation {
  int from, to, p;
  reservation(int from, int to, int p) :
      from(from),
      to(to),
      p(p) {}
};

struct event {
  int at_time, id, p, to_time;
  char action;
  static event create_compelling_event(int at_time, int p, int to_time) {
    event ev;
    ev.at_time = at_time;
    ev.p = p;
    ev.to_time = to_time;
    ev.action = 'C';
    return ev;
  }
  
  static event create_awaiting_event(int at_time, int p, int id) {
    event ev;
    ev.at_time = at_time;
    ev.p = p;
    ev.id = id;
    ev.action = 'A';
    return ev;
  }
  
  static bool order(event const& A, event const& B) {
    if (A.at_time == B.at_time) {
      return A.action < B.action;
    }
    return A.at_time < B.at_time;
  }
};

template<class A, class B>
class greater_second {
public:
  bool operator()(pair<A, B> const& a, pair<A, B> const& b) {
    return a.second > b.second;
  }
};

vector<reservation> reservations;
vector<pair<int, int> > product_id;
vector<vector<int> > group_events;
vector<event> events;

int main() {
  int n, k, a, b, p;
  scanf("%d%d", &n, &k);
  REP(i, n) {
    scanf("%d%d%d", &a, &b, &p);
    reservations.push_back(reservation(a, b, p));
    product_id.push_back(make_pair(p, i));
  }
  sort(product_id.begin(), product_id.end());
  int new_p = -1, last_p = -1;
  REP(i, product_id.size()) {
    if (last_p != product_id[i].first) {
      last_p = product_id[i].first;
      new_p++;
    }
    reservations[product_id[i].second].p = new_p;
  }
  k = new_p + 1;
  
  group_events = vector<vector<int> >(k);
  REP(i, n) {
    group_events[reservations[i].p].push_back(reservations[i].to);
  }
  REP(i, k) {
    sort(group_events[i].begin(), group_events[i].end());
    reverse(group_events[i].begin(), group_events[i].end());
  }
  
  REP(i, n) {
    events.push_back(event::create_awaiting_event(
        reservations[i].from,
        reservations[i].p,
        i));
  }
  REP(i, k) {
    int last_taken = group_events[i][0] + 1;
    for (int at_time : group_events[i]) {
      if (last_taken <= at_time) {
        --last_taken;
      } else {
        last_taken = at_time;
      }
      events.push_back(event::create_compelling_event(last_taken, i, at_time));
    }
  }
  
  vector<int> assignment(n, 0);
  vector<int> scheduled_cnt(k, 0);
  vector<int> taken_down(k, 0);
  vector<priority_queue<pair<int, int>, vector<pair<int, int> >, greater_second<int, int> > > awaiting_ids(k);
  sort(events.begin(), events.end(), event::order);
  bool solution_exists = true;
  int moments = 0;
  for (event ev : events) {
    if (ev.action == 'A') {
      awaiting_ids[ev.p].push(make_pair(ev.id, reservations[ev.id].to));
    } else {
      ++scheduled_cnt[ev.p];
      if (awaiting_ids[ev.p].empty()) {
        if (scheduled_cnt[ev.p] > taken_down[ev.p]) {
          solution_exists = false;
          break;
        }
      } else {
        if (!awaiting_ids[ev.p].empty() && reservations[awaiting_ids[ev.p].top().first].to == ev.to_time) {
          moments++;
          REP(i, k) {
            if (!awaiting_ids[i].empty()) {
              int id = awaiting_ids[i].top().first;
              awaiting_ids[i].pop();
              assignment[id] = ev.at_time;
              taken_down[i]++;
            }
          }
        }
      }
    }
  }
  if (solution_exists) {
    printf("%d\n", moments);
    REP(i, n) {
      printf("%d\n", assignment[i]);
    }
  } else {
    printf("NIE\n");
  }
  return 0;
}