#include <iostream>
#include <map>
#include <set>
using namespace std;

int main() {
  int H, W;
  cin >> H >> W;
  map<int, int> m;
  multiset<int> s;
  for (int w = 1; w <= W; ++w) {
    m[w] = w;
    s.insert(0);
  }

  int a, b;
  for (int h = 1; h <= H; ++h) {
    cin >> a >> b;
    auto it = m.lower_bound(a);
    int mx = -1;
    while (it != m.end() && it->first <= b + 1) {
      mx = max(mx, it->second);
      int d = it->first - it->second;
      s.erase(s.find(d));
      m.erase(it++);
    }

    if (mx != -1 && b + 1 <= W) {
      s.insert(b+1 - mx);
      m[b+1] = mx;
    }
    if (s.empty()) {
      cout << -1 << '\n';
    } else {
      cout << *s.begin() + h << '\n';
    }
  }
  return 0;
}


#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("unroll-loops") 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#define int long long
#define fr(i,a,b) for(int i = a ; i <= b ; ++i)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define pb push_back
#define fst first
#define snd second
using namespace __gnu_pbds;
using ordered_set =
 tree<int, null_type,less<int>,
 rb_tree_tag,tree_order_statistics_node_update>;
//find_by_order(k):returns iterator to kth element starting from 0
//order_of_key(k):returns count of elements strictly smaller than k
typedef long long ll;typedef pair<int, int> pii;
typedef vector<int> vi;typedef long double ld;
template<class T>
using min_heap = priority_queue<T,vector<T>,greater<T>>; 
template<typename T> T gcd(T a, T b){return(b?__gcd(a,b):a);}
template<typename T> T lcm(T a, T b){return(a*(b/gcd(a,b)));}
template<typename T> 
void remdup(vector<T>& v) {
	sort(all(v)); v.erase(unique(all(v)), v.end());
}
template<typename T> void re(vector<T> &v) {trav(i,v) cin >> i;}
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
#ifdef np
#include "C:\Users\navodit\Desktop\mycodes\pr.h"
#else
#define trace(...)
#endif

#define MOD 1000000007  





void solve(){
	int n , m; 
	cin >> n >> m; 
	int cnt = 0;
	vi v(n+1);
	rep(i,0,m){
		int l ,r ;
		cin >> l >> r;
		l--;
		v[l]++;
		v[r]--;
	}
	rep(i,0,n) v[i+1] += v[i];
	rep(i,0,n) cnt+=(v[i]==m);
	cout << cnt << endl;
	
}

signed main() {
	unsyncIO();
	int tt =1 ;
	// cin >> tt;
	rep(i,0,tt) solve();













#ifdef np
	cout <<endl<<endl<< "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}
