output_description: Print H lines. The i-th line should contain the answer for the case k=i.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      H W
      A_1 B_1
      A_2 B_2
      :
      A_H B_H
attempt: import sys
  
  input = sys.stdin.readline
  
  H, W = map(int, input().split())
  D = [tuple(map(int, input().split())) for i in range(H)]
  
  # 範囲更新、最大値取得の遅延セグ木と、範囲更新、最小値取得の遅延セグ木
  
  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
  
      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 = D[i]
      if x == 1:
          updates(x, y + 1, -1)
      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))
  
      # print(*[getvalues(i,i+1) for i in range(W+1)])
      # print(*[getvalues2(i,i+1) for i in range(W+1)])
  
      ANS = getvalues2(1, W + 1) + i + 1
      if ANS > 1 << 28:
          print(-1)
      else:
          print(ANS)
  
problem_description: 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.
samples: [{"input": "4 4\n    2 4\n    1 1\n    2 3\n    2 4", "output": "1\n    3\n    6\n    -1\n    \n\nLet (i,j) denote the square at the i-th row from the top and j-th column from\nthe left.\n\nFor k=1, we need one move such as (1,1) \u2192 (2,1).\n\nFor k=2, we need three moves such as (1,1) \u2192 (2,1) \u2192 (2,2) \u2192 (3,2).\n\nFor k=3, we need six moves such as (1,1) \u2192 (2,1) \u2192 (2,2) \u2192 (3,2) \u2192 (3,3) \u2192\n(3,4) \u2192 (4,4).\n\nFor k=4, it is impossible to reach any square in the fifth row from the top."}]