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
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

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

# 範囲更新、最大値取得の遅延セグ木と、範囲更新、最小値取得の遅延セグ木

seg_el=1<<((W+3).bit_length()) # Segment treeの台の要素数
SEG=[1<<30]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化
LAZY=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

SEG2=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化
LAZY2=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

def indexes(L,R):
    INDLIST=[]

    R-=1
    
    L>>=1
    R>>=1

    while L!=R:
        if L>R:
            INDLIST.append(L)
            L>>=1
        else:
            INDLIST.append(R)
            R>>=1

    while L!=0:
        INDLIST.append(L)
        L>>=1

    return INDLIST
        

def updates(l,r,x): # 区間[l,r)をxに更新
        
    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY[ind]!=None:
            LAZY[ind<<1]=LAZY[1+(ind<<1)]=SEG[ind<<1]=SEG[1+(ind<<1)]=LAZY[ind]
            LAZY[ind]=None
    
    while L!=R:
        if L > R:
            SEG[L]=x
            LAZY[L]=x
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            SEG[R]=x
            LAZY[R]=x
            R//=(R & (-R))

    for ind in UPIND:
        SEG[ind]=max(SEG[ind<<1],SEG[1+(ind<<1)])

def updates2(l,r,x): # 区間[l,r)をxに更新
        
    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY2[ind]!=None:
            LAZY2[ind<<1]=LAZY2[1+(ind<<1)]=SEG2[ind<<1]=SEG2[1+(ind<<1)]=LAZY2[ind]
            LAZY2[ind]=None
    
    while L!=R:
        if L > R:
            SEG2[L]=x
            LAZY2[L]=x
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            SEG2[R]=x
            LAZY2[R]=x
            R//=(R & (-R))

    for ind in UPIND:
        SEG2[ind]=min(SEG2[ind<<1],SEG2[1+(ind<<1)]) 
        
def getvalues(l,r): # 区間[l,r)に関するmaxを調べる

    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY[ind]!=None:
            LAZY[ind<<1]=LAZY[1+(ind<<1)]=SEG[ind<<1]=SEG[1+(ind<<1)]=LAZY[ind]
            LAZY[ind]=None
            
    ANS=-1<<30

    while L!=R:
        if L > R:
            ANS=max(ANS , SEG[L])
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            ANS=max(ANS , SEG[R])
            R//=(R & (-R))

    return ANS

def getvalues2(l,r): # 区間[l,r)に関するminを調べる

    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY2[ind]!=None:
            LAZY2[ind<<1]=LAZY2[1+(ind<<1)]=SEG2[ind<<1]=SEG2[1+(ind<<1)]=LAZY2[ind]
            LAZY2[ind]=None
            
    ANS=1<<31

    while L!=R:
        if L > R:
            ANS=min(ANS , SEG2[L])
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            ANS=min(ANS , SEG2[R])
            R//=(R & (-R))

    return ANS

for i in range(W+1):
    updates(i,i+1,i)

for i in range(H):
    x,y = map(int,input().split())
    if x==1:
        updates(x,y+1,-(1<<30))
    else:
        MAX=getvalues(1,x)
        updates(x,y+1,MAX)

    updates2(x,y+1,1<<30)
    updates2(y+1,y+2,y+1-getvalues(y+1,y+2))

    ANS=getvalues2(1,W+1)+i+1
    if ANS>1<<28:
        sys.stdout.write(str(-1)+"\n")
    else:
        sys.stdout.write(str(ANS)+"\n")