Problem:
 Score : 600 points    Problem Statement There is a grid of squares with H+1 horizontal rows and W vertical columns.  You will start at one of the squares in the top row and repeat moving one square right or down. However, for each integer i from 1 through H , you cannot move down from the A_i -th, (A_i + 1) -th, \ldots , B_i -th squares from the left in the i -th row from the top.  For each integer k from 1 through H , find the minimum number of moves needed to reach one of the squares in the (k+1) -th row from the top. (The starting square can be chosen individually for each case.) If, starting from any square in the top row, none of the squares in the (k+1) -th row can be reached, print -1 instead.      Constraints  1 \leq H,W \leq 2\times 10^5  1 \leq A_i \leq B_i \leq W         Input Input is given from Standard Input in the following format:  H  W  A_1  B_1  A_2  B_2  :  A_H  B_H       Output Print H lines. The i -th line should contain the answer for the case k=i .        Sample Input 1 4 4
2 4
1 1
2 3
2 4      Sample Output 1 1
3
6
-1  Let (i,j) denote the square at the i -th row from the top and j -th column from the left.  For k=1 , we need one move such as (1,1) → (2,1) .  For k=2 , we need three moves such as (1,1) → (2,1) → (2,2) → (3,2) .  For k=3 , we need six moves such as (1,1) → (2,1) → (2,2) → (3,2) → (3,3) → (3,4) → (4,4) .  For k=4 , it is impossible to reach any square in the fifth row from the top.

Solution (Python):
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    inf=10**7
    class LazySegTree:
        def __init__(self, A, initialize=True, segfunc=min, ident=inf):
            self.N = len(A)
            self.LV = (self.N - 1).bit_length()
            self.N0 = 1 << self.LV
            self.segfunc = segfunc
            self.ident = ident
            if initialize:
                self.data = [self.ident] * self.N0 + A + [self.ident] * (self.N0 - self.N)
                for i in range(self.N0 - 1, 0, -1):
                    self.data[i] = segfunc(self.data[i * 2], self.data[i * 2 + 1])
            else:
                self.data = [self.ident] * (self.N0 * 2)
            self.lazy = [0] * (self.N0 * 2)
            self.lazy_flg = [False] * (self.N0 * 2)
 
        def _ascend(self, i):
            for _ in range(i.bit_length() - 1):
                i >>= 1
                self.data[i] = self.segfunc(self.data[i * 2], self.data[i * 2 + 1])
 
        def _descend(self, idx):
            lv = idx.bit_length()
            block_size = 2**self.LV
            for j in range(lv - 1, 0, -1):
                i = idx >> j
                block_size >>= 1
                x = self.lazy[i]
                if not self.lazy_flg[i]:
                    continue
                self.lazy_flg[i] = False
                self.lazy[i * 2] = x
                self.lazy[i * 2 + 1] = x + block_size
                self.lazy_flg[i * 2] = True
                self.lazy_flg[i * 2 + 1] = True
                self.data[i * 2] = x
                self.data[i * 2 + 1] = x + block_size
 
        
        def update(self, l, r, x):
            l += self.N0 - 1
            r += self.N0 - 1
            self._descend(l // (l & -l))
            self._descend(r // (r & -r) - 1)
            l_ori = l
            r_ori = r
            xl = x
            xr = x + (r-l)
            block_size = 1
            while l < r:
                if l & 1:
                    self.data[l] = xl
                    self.lazy[l] = xl
                    self.lazy_flg[l] = True
                    l += 1
                    xl += block_size
                if r & 1:
                    r -= 1
                    xr -= block_size
                    self.data[r] = xr
                    self.lazy[r] = xr
                    self.lazy_flg[r] = True
                l >>= 1
                r >>= 1
                block_size <<= 1
            self._ascend(l_ori // (l_ori & -l_ori))
            self._ascend(r_ori // (r_ori & -r_ori) - 1)
 
        
        def query(self, l, r):
            l += self.N0 - 1
            r += self.N0 - 1
            self._descend(l // (l & -l))
            self._descend(r // (r & -r) - 1)
            ret = self.ident
            while l < r:
                if l & 1:
                    ret = self.segfunc(ret, self.data[l])
                    l += 1
                if r & 1:
                    ret = self.segfunc(self.data[r - 1], ret)
                    r -= 1
                l >>= 1
                r >>= 1
            return ret

    
    H, W = MI()
    ST = LazySegTree([inf] + [0] * W)
    for h in range(H):
        a, b = MI()
        ST.update(a+1, b+2, ST.query(a, a+1)+1)
        
        
        
        
        
        
        ans = ST.query(2, W+2)
        if ans >= inf:
            print(-1)
        else:
            print(h + 1 + ans)


    mod=10**9+7

main()

Solution (Python):






from heapq import *


class MultisetBIT:
    """
    最大値が小さい数について、その重複を許した集合を管理する。
    最大値 maxvalue を受け取り、[0, maxvalue] を管理する。
    閉区間で管理する。
    """

    __slots__ = ["n", "k", "data"]

    def __init__(self, maxvalue):
        "内部では [1, maxvalue + 1] でもつ。"
        self.n = maxvalue + 1
        self.k = 1 << ((self.n + 1).bit_length() - 1)
        self.data = [0] * (self.n + 1)

    def add(self, value):
        """
        与えられた引数を Multiset に加える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        while value <= self.n:
            self.data[value] += 1
            value += value & -value

    def pop(self, value):
        """
        Multiset から与えられた引数を取り除く。
        与えられた引数が Multiset に入っているかのチェックは行わなず、
        単にその個数を 1 減らすだけなので注意。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        while value <= self.n:
            self.data[value] -= 1
            value += value & -value

    def count_le(self, value):
        """
        Multiset 内の要素 elem のうち、0 <= elem <= value を満たすものを数える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        ret = 0
        while value > 0:
            ret += self.data[value]
            value -= value & -value
        return ret

    def count(self, first, last):
        """
        Multiset 内の要素 elem のうち、first <= elem <= last を満たすものを数える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        last += 1
        ret = 0
        while first < last:
            ret += self.data[last]
            last -= last & -last
        while last < first:
            ret -= self.data[first]
            first -= first & -first
        return ret

    def bisect(self, count):
        """
        Multiset 内の要素 elem のうち、count <= count_le(elem) を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        ret = 0
        k = self.k
        while k > 0:
            if ret + k <= self.n and self.data[ret + k] < count:
                count -= self.data[ret + k]
                ret += k
            k >>= 1
        return ret


    def lower_bound(self, value):
        """
        Multiset 内の要素 elem のうち、value <= elem を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        return self.bisect(self.count_le(value - 1) + 1)

    def upper_bound(self, value):
        """
        Multiset 内の要素 elem のうち、value < elem を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        return self.bisect(self.count_le(value) + 1)


H, W = map(int, input().split())

destination = MultisetBIT(W)
for i in range(W):
    destination.add(i)

destination_to_cost = {i:0 for i in range(W)}

min_heapq = [0] * W
to_delete = []

for k in range(H):
    
    
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    start_point = destination.lower_bound(A)
    point = start_point
    change_dest_flg = False
    while point < W and point < B + 1:
        change_dest_flg = True
        cost = destination_to_cost.pop(point)
        heappush(to_delete, cost)
        if B + 1 != W:
            if (B + 1 in destination_to_cost):
                if destination_to_cost[B+1] > (B + 1 - point) + cost:
                    heappush(to_delete, destination_to_cost[B+1])
                    destination_to_cost[B+1] = (B + 1 - point) + cost
                    heappush(min_heapq, (B + 1 - point) + cost)
            else:
                destination_to_cost[B+1] = (B + 1 - point) + cost
                heappush(min_heapq, (B + 1 - point) + cost)
                destination.add(B+1)
        destination.pop(point)
        point = destination.upper_bound(point)

    while to_delete and min_heapq[0] == to_delete[0]:
        heappop(min_heapq)
        heappop(to_delete)
    
    if min_heapq:
        print(k + min_heapq[0] + 1)
    else:
        for _ in range(H - k):
            print(-1)
        exit()

Solution (Python):

import sys 
import heapq
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 

def main():
    
    class BIT:
        def __init__(self,len_A):
            self.N = len_A + 10
            self.bit = [0]*(len_A+10)
        
        
        def query(self,i):
            res = 0
            idx = i+1
            while idx:
                res += self.bit[idx]
                idx -= idx&(-idx)
            return res
        
        
        def update(self,i,x):
            idx = i+1
            while idx < self.N:
                self.bit[idx] += x
                idx += idx&(-idx)
        
        
        def lower_left(self,w):
            if (w < 0):
                return -1
            x = 0
            k = 1<<(self.N.bit_length()-1)
            while k > 0:
                if x+k < self.N and self.bit[x+k] < w:
                    w -= self.bit[x+k]
                    x += k
                k //= 2
            return x
 
    h,w = map(int,readline().split())
    
    dp = [0]*(w+1)
    
    res = [0]*w
    
    anti = []
    C = BIT(w)
    for i in range(1,w+1):
        C.update(i,1)
    for i in range(1,h+1):
        a,b = map(int,readline().split())
        
        x = a-1
        if x != 0 and x != w+1 and dp[x] == -1:
            
            k = C.query(x-1)
            
            if k != 0:
                ok = C.lower_left(k)
                
                dp[x] = dp[ok] + (x-ok)
                C.update(x,1)
                heapq.heappush(res,dp[x])
                
        x = b+1
        if x != 0 and x != w+1 and dp[x] == -1:
            
            k = C.query(x-1)
            
            if k != 0:
                ok = C.lower_left(k)
                
                dp[x] = dp[ok] + (x-ok)
                C.update(x,1)
                heapq.heappush(res,dp[x])
        k = C.query(a-1)+1
 
        while True:
            ok = C.lower_left(k)
            if ok > b or dp[ok] == -1:
                break
            heapq.heappush(anti,dp[ok])
            dp[ok] = -1
            C.update(ok,-1)
        while anti and res and anti[0] == res[0]:
            heapq.heappop(anti)
            heapq.heappop(res)
        if res:
            print(res[0]+i)
        else:
            print(-1)
if __name__ == '__main__':
    main()

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"
INF = 1<<32-1

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

class Binary_Indexed_Tree:
    '''
    Binary_Indexed_Tree
    A1 ... AnのBIT(1-indexed)
    std_mapを使うときには一緒に貼る
    '''
    def __init__(self,n):
        self.N = n
        self.BIT = [0]*(n+1)
        self.l2 = 2**(len(format(n,'b'))-1)

    
    def get_sum(self,idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    
    def query(self,l,r):
        return self.get_sum(r)-self.get_sum(l-1)

    
    def add(self,idx,x):
        while idx <= self.N:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return

    
    def lower_bound(self,w):
        if w <= 0:
            return 0
        x = 0
        k = self.l2
        while k > 0:
            if x+k <= self.N and self.BIT[x+k] < w:
                w -= self.BIT[x+k]
                x += k
            k //= 2
        return x+1

    
    def upper_bound(self,w):
        x = 0
        k = self.l2
        while k > 0:
            if x+k <= self.N and self.BIT[x+k] <= w:
                w -= self.BIT[x+k]
                x += k
            k //= 2
        return x+1

class std_map:
    '''
    c++のstd::map(平衡二分探索木)
    dictにおいてkeyの範囲が限定されてkeyに順序が組み込まれたもの
    念願のlower_boundとupper_boundができるようになった
    '''

    def __init__(self,n,init):
        self.size = n
        self.keys = set()
        self.bit = Binary_Indexed_Tree(n+1)
        self.dic = [init]*(n+1)

    def __contains__(self,key): 
        return key in self.keys

    def __getitem__(self,key): 
        return self.dic[key]

    def __setitem__(self,key,value): 
        if not key in self.keys:
            self.bit.add(key,1)
            self.keys.add(key)
        self.dic[key] = value

    def remove(self,key): 
        self.keys.remove(key)
        self.bit.add(key,-1)

    def lower_bound(self,k): 
        return self.bit.lower_bound(self.bit.get_sum(k))

    def upper_bound(self,k): 
        return self.bit.upper_bound(self.bit.get_sum(k))

    def kth_key(self,k): 
        return self.bit.lower_bound(k)

    def kth_value(self,k): 
        return self.dic[self.kth_key(k)]

    def prev_k(self,k): 
        idx = self.bit.get_sum(k)
        if idx == 0:
            return -1
        return self.bit.lower_bound(idx-1)

    def prev_k(self,k): 
        idx = self.bit.get_sum(k)
        if idx == self.size:
            return -1
        return self.bit.lower_bound(idx+1)

def main():
    h,w = map(int,ipt().split())
    st = SegTree([INF]+[0]*w+[INF],min,INF)
    s = std_map(w+2,0)
    for i in range(1,w+2):
        s.bit.add(i,1)
    s.keys = set(range(1,w+2))


    for i in range(h):
        a,b = map(int,ipt().split())
        pl = s.bit.get_sum(a-1)+1

        pa = s.kth_key(pl)
        mv = INF
        while pa <= b:

            st.update(pa,INF)
            mv = min(mv,s[pa]-pa)
            s.remove(pa)
            pa = s.kth_key(pl)



        mv += b+1
        if b != w:
            if (not b+1 in s) or s[b+1] > mv:
                st.update(b+1,mv)
                s[b+1] = mv

        mv = st.tree[1]
        if mv == INF:
            print(-1)
        else:
            print(mv+i+1)

    return None

if __name__ == '__main__':
    main()

Solution (Python):
import sys,heapq
input = sys.stdin.buffer.readline




def main():
    h,w = map(int,input().split())


    class BIT:
        def __init__(self,len_A):
            self.N = len_A + 10
            self.bit = [0]*(len_A+10)
            
        
        
        def query(self,i):
            res = 0
            idx = i+1
            while idx:
                res += self.bit[idx]
                idx -= idx&(-idx)
            return res

        
        
        def update(self,i,x):
            idx = i+1
            while idx < self.N:
                self.bit[idx] += x
                idx += idx&(-idx)
        
        
        
        def lower_left(self,w):
            if (w < 0):
                return -1
            x = 0
            k = 1<<(self.N.bit_length()-1)
            while k > 0:
                if x+k < self.N and self.bit[x+k] < w:
                    w -= self.bit[x+k]
                    x += k
                k //= 2
            return x


    
    dp = [0]*(w+1)

    
    res = [0]*w

    
    anti = []

    C = BIT(w)

    for i in range(1,w+1):
        C.update(i,1)

    for i in range(1,h+1):
        a,b = map(int,input().split())
        
        
        x = a-1
        if x != 0 and x != w+1 and dp[x] == -1:
            
            k = C.query(x-1)

            
            if k != 0:
                ok = C.lower_left(k)
                
                dp[x] = dp[ok] + (x-ok)
                C.update(x,1)
                heapq.heappush(res,dp[x])
                
        x = b+1
        if x != 0 and x != w+1 and dp[x] == -1:
            
            k = C.query(x-1)

            
            if k != 0:
                ok = C.lower_left(k)
                
                dp[x] = dp[ok] + (x-ok)
                C.update(x,1)
                heapq.heappush(res,dp[x])

        k = C.query(a-1)+1

        while True:
            ok = C.lower_left(k)
            if ok > b or dp[ok] == -1:
                break
            
            heapq.heappush(anti,dp[ok])
            dp[ok] = -1
            C.update(ok,-1)
        
        while anti and res and anti[0] == res[0]:
            heapq.heappop(anti)
            heapq.heappop(res)

        if res:
            print(res[0]+i)
        else:
            print(-1)

if __name__ == '__main__':
    main()

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

class Binary_Indexed_Tree:
    '''
    Binary_Indexed_Tree
    A1 ... AnのBIT(1-indexed)
    std_mapを使うときには一緒に貼る
    '''
    def __init__(self,n):
        self.N = n
        self.BIT = [0]*(n+1)
        self.l2 = 2**(len(format(n,'b'))-1)

    
    def get_sum(self,idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    
    def query(self,l,r):
        return self.get_sum(r)-self.get_sum(l-1)

    
    def add(self,idx,x):
        while idx <= self.N:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return

    
    def lower_bound(self,w):
        if w <= 0:
            return 0
        x = 0
        k = self.l2
        while k > 0:
            if x+k <= self.N and self.BIT[x+k] < w:
                w -= self.BIT[x+k]
                x += k
            k //= 2
        return x+1

    
    def upper_bound(self,w):
        x = 0
        k = self.l2
        while k > 0:
            if x+k <= self.N and self.BIT[x+k] <= w:
                w -= self.BIT[x+k]
                x += k
            k //= 2
        return x+1

class std_map:
    '''
    c++のstd::map(平衡二分探索木)
    dictにおいてkeyの範囲が限定されてkeyに順序が組み込まれたもの
    念願のlower_boundとupper_boundができるようになった
    '''

    def __init__(self,n,init):
        self.size = n
        self.keys = set()
        self.bit = Binary_Indexed_Tree(n+1)
        self.dic = [init]*(n+1)

    def __contains__(self,key): 
        return key in self.keys

    def __getitem__(self,key): 
        return self.dic[key]

    def __setitem__(self,key,value): 
        if not key in self.keys:
            self.bit.add(key,1)
            self.keys.add(key)
        self.dic[key] = value

    def remove(self,key): 
        self.keys.remove(key)
        self.bit.add(key,-1)

    def lower_bound(self,k): 
        return self.bit.lower_bound(self.bit.get_sum(k))

    def upper_bound(self,k): 
        return self.bit.upper_bound(self.bit.get_sum(k))

    def kth_key(self,k): 
        return self.bit.lower_bound(k)

    def kth_value(self,k): 
        return self.dic[self.kth_key(k)]

    def prev_k(self,k): 
        idx = self.bit.get_sum(k)
        if idx == 0:
            return -1
        return self.bit.lower_bound(idx-1)

    def prev_k(self,k): 
        idx = self.bit.get_sum(k)
        if idx == self.size:
            return -1
        return self.bit.lower_bound(idx+1)

def main():
    h,w = map(int,ipt().split())
    st = SegTree([10**18]+[0]*w+[10**18],min,10**18)
    s = std_map(w+2,0)
    for i in range(1,w+2):
        s.bit.add(i,1)
    s.keys = set(range(1,w+2))


    for i in range(h):
        a,b = map(int,ipt().split())
        pl = s.bit.get_sum(a-1)+1

        pa = s.kth_key(pl)
        mv = 10**18
        while pa <= b:

            st.update(pa,10**18)
            mv = min(mv,s[pa]-pa)
            s.remove(pa)
            pa = s.kth_key(pl)



        mv += b+1
        if b != w:
            if (not b+1 in s) or s[b+1] > mv:
                st.update(b+1,mv)
                s[b+1] = mv

        mv = st.tree[1]
        if mv == 10**18:
            print(-1)
        else:
            print(mv+i+1)

    return None

if __name__ == '__main__':
    main()

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

class Binary_Indexed_Tree:
    '''
    Binary_Indexed_Tree
    A1 ... AnのBIT(1-indexed)
    std_mapを使うときには一緒に貼る
    '''
    def __init__(self,n):
        self.N = n
        self.BIT = [0]*(n+1)
        self.l2 = 2**(len(format(n,'b'))-1)

    
    def get_sum(self,idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    
    def query(self,l,r):
        return self.get_sum(r)-self.get_sum(l-1)

    
    def add(self,idx,x):
        while idx <= self.N:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return

    
    def lower_bound(self,w):
        if w <= 0:
            return 0
        x = 0
        k = self.l2
        while k > 0:
            if x+k <= self.N and self.BIT[x+k] < w:
                w -= self.BIT[x+k]
                x += k
            k //= 2
        return x+1

    
    def upper_bound(self,w):
        x = 0
        k = self.l2
        while k > 0:
            if x+k <= self.N and self.BIT[x+k] <= w:
                w -= self.BIT[x+k]
                x += k
            k //= 2
        return x+1

class std_map:
    '''
    c++のstd::map(平衡二分探索木)
    dictにおいてkeyの範囲が限定されてkeyに順序が組み込まれたもの
    念願のlower_boundとupper_boundができるようになった
    '''

    def __init__(self,n,init):
        self.size = n
        self.keys = set()
        self.bit = Binary_Indexed_Tree(n+1)
        self.dic = [init]*(n+1)

    def __contains__(self,key): 
        return key in self.keys

    def __getitem__(self,key): 
        return self.dic[key]

    def __setitem__(self,key,value): 
        if not key in self.keys:
            self.bit.add(key,1)
            self.keys.add(key)
        self.dic[key] = value

    def remove(self,key): 
        self.keys.remove(key)
        self.bit.add(key,-1)

    def lower_bound(self,k): 
        return self.bit.lower_bound(self.bit.get_sum(k))

    def upper_bound(self,k): 
        return self.bit.upper_bound(self.bit.get_sum(k))

    def kth_key(self,k): 
        return self.bit.lower_bound(k)

    def kth_value(self,k): 
        return self.dic[self.kth_key(k)]

    def prev_k(self,k): 
        idx = self.bit.get_sum(k)
        if idx == 0:
            return -1
        return self.bit.lower_bound(idx-1)

    def prev_k(self,k): 
        idx = self.bit.get_sum(k)
        if idx == self.size:
            return -1
        return self.bit.lower_bound(idx+1)

def main():
    h,w = map(int,ipt().split())
    st = SegTree([10**18]+[0]*w+[10**18],min,10**18)
    s = std_map(w+2,0)
    for i in range(1,w+2):
        s.bit.add(i,1)
    s.keys = set(range(w+2))


    for i in range(h):
        a,b = map(int,ipt().split())
        pl = s.bit.get_sum(a-1)+1

        pa = s.kth_key(pl)
        mv = 10**18
        while pa <= b:

            st.update(pa,10**18)
            mv = min(mv,s[pa]-pa)
            s.remove(pa)
            pa = s.kth_key(pl)



        mv += b+1
        if b != w:
            if (not b+1 in s) or s[b+1] > mv:
                st.update(b+1,mv)
                s[b+1] = mv

        mv = st.tree[1]
        if mv == 10**18:
            print(-1)
        else:
            print(mv+i+1)

    return None

if __name__ == '__main__':
    main()