#include #if __has_include() #include std::istream &operator>>(std::istream &is, atcoder::modint &v) { long long value; is >> value; v = value; return is; } std::ostream &operator<<(std::ostream &os, const atcoder::modint &v) { os << v.val(); return os; } std::ostream &operator<<(std::ostream &os, const atcoder::modint998244353 &v) { os << v.val(); return os; } std::istream &operator>>(std::istream &is, atcoder::modint998244353 &v) { long long x; is >> x; v = x; return is; } std::ostream &operator<<(std::ostream &os, const atcoder::modint1000000007 &v) { os << v.val(); return os; } std::istream &operator>>(std::istream &is, atcoder::modint1000000007 &v) { long long x; is >> x; v = x; return is; } #endif using namespace std; using ll = long long; using pll = pair; #define newl '\n'; #define rep(i, s, t) for (ll i = s; i < (ll)(t); i++) #define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--) #define all(x) begin(x), end(x) #define eb emplace_back #define pb push_back #define TT template TT using vec = vector; TT using vvec = vec>; TT using vvvec = vec>; TT using minheap = priority_queue, greater>; TT using maxheap = priority_queue; TT bool chmin(T &x, T y) { return x > y ? (x = y, true) : false; } TT bool chmax(T &x, T y) { return x < y ? (x = y, true) : false; } TT bool rng(T l, T x, T r) { return l <= x && x < r; } TT T flr(T a, T b) { if (b < 0) a = -a, b = -b; return a >= 0 ? a / b : (a + 1) / b - 1; } TT T cil(T a, T b) { if (b < 0) a = -a, b = -b; return a > 0 ? (a - 1) / b + 1 : a / b; } TT T sqr(T x) { return x * x; } struct io_setup { io_setup() { ios::sync_with_stdio(false); std::cin.tie(nullptr); cout << fixed << setprecision(15); } } io_setup; template ostream &operator<<(ostream &os, const pair &p) { os << p.first << " " << p.second; return os; } TT ostream &operator<<(ostream &os, const vec &v) { for (size_t i = 0; i < v.size(); i++) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; } template ostream &operator<<(ostream &os, const array &v) { for (size_t i = 0; i < n; i++) { os << v[i] << (i + 1 != n ? " " : ""); } return os; } template ostream &operator<<(ostream &os, const vvec &v) { for (size_t i = 0; i < v.size(); i++) { os << v[i] << (i + 1 != v.size() ? "\n" : ""); } return os; } TT istream &operator>>(istream &is, vec &v) { for (size_t i = 0; i < v.size(); i++) { is >> v[i]; } return is; } #if __has_include() #include #else #define dbg(...) true #define DBG(...) true #define OUT(...) true #endif template struct rangeset : public std::map { rangeset() {} auto get(T p) const { auto it = (*this).upper_bound(p); if (it == (*this).begin() || (--it)->second <= p) return (*this).end(); return it; } //[l, r) void insert(T l, T r) { if (l == r) return; assert(l <= r); auto itl = (*this).upper_bound(l), itr = (*this).lower_bound(r + merge_adju); if (itl != (*this).begin() && (--itl)->second + merge_adju <= l) { ++itl; } if (itl != itr) { if (itl->first < l) l = itl->first; if (prev(itr)->second > r) r = prev(itr)->second; map::erase(itl, itr); } (*this)[l] = r; } //[l, r) void erase(T l, T r) { if (l == r) return; assert(l <= r); auto itl = (*this).upper_bound(l), itr = (*this).lower_bound(r); if (itl != (*this).begin() && (--itl)->second <= l) { ++itl; } if (itl == itr) return; T tl = l, tr = r; if (itl->first < l) tl = itl->first; if (prev(itr)->second > r) tr = prev(itr)->second; map::erase(itl, itr); if (tl < l) (*this)[tl] = l; if (tr > r) (*this)[r] = tr; } bool contains(T p) const { return get(p) != (*this).end(); } bool same(T a, T b) const { if (a > b) swap(a, b); auto it = get(a); if (it == (*this).end()) return false; return b < it->second; } T mex(T x = 0) const { auto it = get(x); if(it == (*this).end()) return x; else return it -> second; } template friend ostream &operator<<(ostream &os, rangeset const &rhs) { for (auto [l, r] : rhs) os << "[" << l << ", " << r << ")"; return os; } }; int main() { ll d, q; cin >> d >> q; rangeset rs; ll ans = 0; while(q--) { ll a, b; cin >> a >> b; b++; rs.insert(a, b); auto it = rs.get(a); chmax(ans, it -> second - it -> first); cout << ans << newl; } }