# Original solution
import sys,heapq
input = sys.stdin.buffer.readline


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


    #dp[i] : iの時の最小右移動回数
    dp = [0]*(w+1)


    #解候補
    res = [0]*w

    #解候補から消されるもの
    anti = []



    #Ai = {1:dp[i]はvalid 0:invalid}

    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(w+100)

    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= w:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    for i in range(1,w+1):
        BIT_update(i,1)


    for i in range(1,h+1):
        a,b = list(map(int,input().split()))
        
        #a-1,b+1の値を計算
        for x in [a-1,b+1]:
            #端で操作不可能
            if x in (0,w+1):
                continue

            #validな値の場合そのまま下に行く
            if dp[x] != -1:
                continue
            
            #x以下のvalidな個数
            k = BIT_query(x-1)

            #k番目のvalidな位置okからXに行く
            if k == 0:
                continue
            ok = x
            ng = 0
            while ok-ng > 1:
                mid = (ok+ng)//2
                if BIT_query(mid) == k:
                    ok = mid
                else:
                    ng = mid
            #xをvalidにする
            dp[x] = dp[ok] + (x-ok)
            BIT_update(x,1)
            heapq.heappush(res,dp[x])

        k = BIT_query(a-1)+1

        while True:
            ng = 0
            ok = w
            while ok-ng > 1:
                mid = (ok+ng)//2
                if BIT_query(mid) >= k:
                    ok = mid
                else:
                    ng = mid

            if ok > b or dp[ok] == -1:
                break
            
            heapq.heappush(anti,dp[ok])
            dp[ok] = -1
            BIT_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()

# Optimized solution
import sys,heapq
input = sys.stdin.buffer.readline


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


    #dp[i] : iの時の最小右移動回数
    dp = [0]*(w+1)


    #解候補
    res = [0]*w

    #解候補から消されるもの
    anti = []



    #Ai = {1:dp[i]はvalid 0:invalid}

    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(w+100)

    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= w:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    for i in range(1,w+1):
        BIT_update(i,1)


    for i in range(1,h+1):
        a,b = list(map(int,input().split()))
        
        #a-1,b+1の値を計算
        for x in [a-1,b+1]:
            #端で操作不可能
            if x in (0,w+1):
                continue

            #validな値の場合そのまま下に行く
            if dp[x] != -1:
                continue
            
            #x以下のvalidな個数
            k = BIT_query(x-1)

            #k番目のvalidな位置okからXに行く
            if k == 0:
                continue
            ok = x
            ng = 0
            while ok-ng > 1:
                mid = (ok+ng)//2
                if BIT_query(mid) == k:
                    ok = mid
                else:
                    ng = mid
            #xをvalidにする
            dp[x] = dp[ok] + (x-ok)
            BIT_update(x,1)
            heapq.heappush(res,dp[x])

        k = BIT_query(a-1)+1

        while True:
            ng = a-1
            ok = w
            while ok-ng > 1:
                mid = (ok+ng)//2
                if BIT_query(mid) >= k:
                    ok = mid
                else:
                    ng = mid

            if ok > b or dp[ok] == -1:
                break
            
            heapq.heappush(anti,dp[ok])
            dp[ok] = -1
            BIT_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()