Problem: 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.

Example

Input

4 4
2 4
1 1
2 3
2 4


Output

1
3
6
-1

Solution (in PYTHON3):

Solution:
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)
            
        # sum(A0 ~ Ai)
        # O(log N)
        def query(self,i):
            res = 0
            idx = i+1
            while idx:
                res += self.bit[idx]
                idx -= idx&(-idx)
            return res

        # Ai += x
        # O(log N)
        def update(self,i,x):
            idx = i+1
            while idx < self.N:
                self.bit[idx] += x
                idx += idx&(-idx)
        
        # min_i satisfying {sum(A0 ~ Ai) >= w} (Ai >= 0)
        # O(log N)
        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[i] : iの時の最小右移動回数
    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())
        
        #a-1,b+1の値を計算
        x = a-1
        if x != 0 and x != w+1 and dp[x] == -1:
            #x以下のvalidな個数
            k = C.query(x-1)

            #k番目のvalidな位置okからXに行く
            if k != 0:
                ok = C.lower_left(k)
                #xをvalidにする
                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:
            #x以下のvalidな個数
            k = C.query(x-1)

            #k番目のvalidな位置okからXに行く
            if k != 0:
                ok = C.lower_left(k)
                #xをvalidにする
                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()