#![allow(clippy::many_single_char_names)]
// ngtio {{{
#[allow(dead_code)]
mod ngtio {
    use ::std::collections::VecDeque;

    pub struct Buffer {
        buf: VecDeque<String>,
    }

    impl Buffer {
        pub fn new() -> Self {
            Self {
                buf: VecDeque::new(),
            }
        }

        fn load(&mut self) {
            while self.buf.is_empty() {
                let mut s = String::new();
                let length = ::std::io::stdin().read_line(&mut s).unwrap();
                if length == 0 {
                    break;
                }
                self.buf.extend(s.split_whitespace().map(|s| s.to_owned()));
            }
        }

        pub fn string(&mut self) -> String {
            self.load();
            self.buf
                .pop_front()
                .unwrap_or_else(|| panic!("入力が終了したのですが。"))
        }

        pub fn char(&mut self) -> char {
            let string = self.string();
            let mut chars = string.chars();
            let res = chars.next().unwrap();
            assert!(
                chars.next().is_none(),
                "char で受け取りたいのも山々なのですが、さては 2 文字以上ありますね？"
            );
            res
        }

        pub fn read<T: ::std::str::FromStr>(&mut self) -> T
        where
            <T as ::std::str::FromStr>::Err: ::std::fmt::Debug,
        {
            self.string()
                .parse::<T>()
                .expect("Failed to parse the input.")
        }

        pub fn read_vec<T: ::std::str::FromStr>(&mut self, len: usize) -> Vec<T>
        where
            <T as ::std::str::FromStr>::Err: ::std::fmt::Debug,
        {
            (0..len).map(|_| self.read::<T>()).collect()
        }
    }

    macro_rules! define_primitive_reader {
        ($($ty:tt,)*) => {
            impl Buffer {
                $(
#[inline]
                    pub fn $ty(&mut self) -> $ty {
                        self.read::<$ty>()
                    }
                )*
            }
        }
    }

    define_primitive_reader! {
        u8, u16, u32, u64, usize,
        i8, i16, i32, i64, isize,
    }

    impl Default for Buffer {
        fn default() -> Self {
            Self::new()
        }
    }
}
// }}}

fn main() {
    let mut buf = ngtio::Buffer::new();
    let h = buf.usize();
    let w = buf.usize();

    let mut map = (0..w)
        .map(|i| (i, i))
        .collect::<std::collections::BTreeMap<_, _>>();
    let mut ng = false;
    let mut ckd = vec![0; w];
    ckd[0] = w;
    let mut diffs = std::collections::BTreeSet::new();
    diffs.insert(0);

    for i in 0..h {
        if ng {
            println!("-1");
            continue;
        }
        let l = buf.usize() - 1;
        let r = buf.usize();
        let subrange = map
            .range(l..r)
            .map(|(&x, &y)| (x, y))
            .collect::<Vec<(usize, usize)>>();

        for &(key, value) in &subrange {
            map.remove(&key);
            let dif = key - value;
            ckd[dif] -= 1;
            if ckd[dif] == 0 {
                let res = diffs.remove(&dif);
                assert!(res);
            }
        }
        if let Some(&(end, start)) = subrange.last() {
            assert!((l..r).contains(&end));
            if r < w && !map.contains_key(&r) {
                map.insert(r, start);
                let dif = r - start;
                if ckd[dif] == 0 {
                    diffs.insert(dif);
                }
                ckd[dif] += 1;
            }
        }
        if let Some(ans) = diffs.iter().next() {
            println!("{}", ans + i + 1);
        } else {
            ng = true;
            println!("-1");
        }
    }
}

/*
 * 各 i, j について (0, start) -> (i, j) が到達可能である最大の start を f(i, j) としましょう。
 * これは j に関して単調増加で、i に関して単調減少です。
 * j に関して一定である区間を、左端で代表しましょう。
 * すると、更新は削除たくさん挿入一つです。
 * また j - f(i, j) のチェックリストと最大を管理しておきましょう。「
 * 答えは i + 最大です。
 */


Measured memory_bytes: 10296