#pragma region Macros // #pragma GCC target("avx2") #pragma GCC optimize("O3") #include #include using namespace std; struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<= 0; i--) #define ALL(v) v.begin(), v.end() #define endl "\n" #define fi first #define se second #define popcount(bit) __builtin_popcount(bit) #define popcountll(bit) __builtin_popcountll(bit) #define pb push_back #define eb emplace_back using namespace atcoder; using P = pair; using PP = pair; using PL = pair; using Graph = vector>; typedef long long ll; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } const int dx[4] = {1, 0, -1, 0}; const int dy[4] = {0, 1, 0, -1}; const int fx[8] = {0, 1, 1, 1, 0, -1, -1, -1}; const int fy[8] = {1, 1, 0, -1, -1, -1, 0, 1}; template const auto INF = numeric_limits::max()/2; template struct RangeSet{ set> st; T TINF; RangeSet(){ TINF=(int)(1e9+ 1); st.emplace(TINF,TINF); st.emplace(-TINF,-TINF); } // [l,r] covered? bool covered(T l,T r){ assert(l<=r); auto ite=prev(st.lower_bound({l+1,l+1})); return ite->first<=l and r<=ite->second; } bool covered(T x){ return covered(x,x); } // [l, r]がカバーされているなら,その区間を返す. されていないなら[-TINF,-TINF]を返す pair covered_by(T l,T r){ assert(l<=r); auto ite=prev(st.lower_bound({l+1,l+1})); if(ite->first<=l and r<=ite->second) return *ite; return make_pair(-TINF,-TINF); } pair covered_by(T x){ return covered_by(x,x); } // insert[l,r], 増加量を返す T insert(T l,T r){ assert(l<=r); auto ite=prev(st.lower_bound({l+1,l+1})); if(ite->first<=l and r<=ite->second) return T(0); T sum_erased=T(0); if(ite->first<=l and l<=ite->second+1){ l=ite->first; sum_erased+=ite->second-ite->first+1; ite=st.erase(ite); }else ite=next(ite); while(r>ite->second){ sum_erased+=ite->second-ite->first+1; ite=st.erase(ite); } if(ite->first-1<=r and r<=ite->second){ sum_erased+=ite->second-ite->first+1; r=ite->second; st.erase(ite); } st.emplace(l,r); return r-l+1-sum_erased; } T insert(T x){ return insert(x,x); } // erase [l,r], 減少量を返す T erase(T l,T r){ assert(l<=r); auto ite=prev(st.lower_bound({l+1,l+1})); if(ite->first<=l and r<=ite->second){ // 完全に1つの区間に包含されている if(ite->firstfirst,l-1); if(rsecond) st.emplace(r+1,ite->second); st.erase(ite); return r-l+1; } T ret=T(0); if(ite->first<=l and l<=ite->second){ ret+=ite->second-l+1;// 消えた if(ite->firstfirst,l-1); ite=st.erase(ite);// 次へ }else ite=next(ite); while(ite->second<=r){ ret+=ite->second-ite->first+1; ite=st.erase(ite); } // 右端が区間の間にあるか if(ite->first<=r and r<=ite->second){ ret+=r-ite->first+1; if(rsecond) st.emplace(r+1,ite->second); st.erase(ite); } return ret; } T erase(T x){ return erase(x,x); } // number of range int size(){ return (int)st.size()-2; } // mex [x,~) T mex(T x=0){ auto ite=prev(st.lower_bound({x+1,x+1})); if(ite->first<=x and x<=ite->second) return ite->second+1; else return x; } void output(){ cout<<"RangeSet : "; for(auto &p:st){ if(p.first==-TINF or p.second==TINF) continue; cout<<"["<> n >> m; vector LR(m); vector ans(n, (int)1e9); segtree seg(ans); RangeSet s; rep(i, m){ int l, r, x; cin >> l >> r >> x; l--, r--; LR[i].se.fi = l; LR[i].se.se = r; LR[i].fi = x; } sort(ALL(LR), [](PP x, PP y){ if(x.se.se - x.se.fi != y.se.se - y.se.fi){ return x.se.se - x.se.fi < y.se.se - y.se.fi; }else if(x.fi != y.fi){ return x.fi < y.fi; }else{ return x.se.fi > y.se.fi; } }); for(auto [x, p] : LR){ auto [l, r] = p; if(seg.prod(l, r+1) == x)continue; if(seg.prod(l, r+1) < x){ cout << -1 << endl; return 0; } int left = s.mex(l); if(r < left){ cout << -1 << endl; return 0; } ans[left] = x; seg.set(left, x); s.insert(left); } rep(i, n){ cout << ans[i] << (i == n - 1 ? "\n" : " "); } }