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 = lambda: sys.stdin.readline().rstrip()
  sys.setrecursionlimit(max(1000, 10**9))
  write = lambda x: sys.stdout.write(x + "\n")
  
  
  h, w = map(int, input().split())
  ab = [tuple(map(int, input().split())) for _ in range(h)]
  dp = [None] * h
  v = 1
  i = 0
  for a, b in ab:
      if a <= v <= b:
          v = b + 1
      dp[i] = v
      i += 1
  dp2 = [None] * h
  done = [0] * h
  for i in range(h - 1, -1, -1):
      if done[i]:
          continue
      v = w
      l = []
      for j in range(i, -1, -1):
          a, b = ab[j]
          if v == w:
              l.append(j)
          if a <= v <= b:
              v = a - 1
      for ind in l:
          dp2[ind] = v
          done[ind] = 1
  dp, dp2
  ans = [None] * h
  for i in range(h):
      if dp[i] > w:
          ans[i] = -1
      else:
          #         if dp[i]>=dp2[i]:
          ans[i] = (i + 1) + (dp[i] - dp2[i])
  write("\n".join(map(str, 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."}]