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 numpy as np
  from numba import njit
  from numba.types import Array, int64
  
  i4 = np.int32
  i8 = np.int64
  
  
  @njit((Array(int64, 1, "C"), Array(int64, 1, "C"), int64, int64), cache=True)
  def solve(a, b, H, W):
      ret = np.empty(H, i8)
      for i in range(H):
          ret[i] = -1
      dp0 = np.arange(W)
      dp = np.arange(W)
      arg0 = W - 1
      arg = 0
      for i in range(H):
          r1 = np.searchsorted(dp, a[i])
          r2 = np.searchsorted(dp, b[i])
          if b[i] == W:
              if r1 == 0:
                  return ret
              else:
                  dp0 = dp0[:r1]
                  dp = dp[:r1]
          else:
              dp[r1:r2] = b[i]
  
          if arg0 > -1:
              if r1 <= arg0 < r2:
                  for j in range(r1 - 1, -1, -1):
                      if dp[j] == dp0[j]:
                          arg0 = j
                          ret[i] = i + 1
                          break
                  else:
                      arg0 = -1
                      arg = np.argmin(dp - dp0)
                      ret[i] = dp[arg] - dp0[arg] + i + 1
              else:
                  ret[i] = i + 1
          else:
              if r1 <= arg < r2:
                  arg = np.argmin(dp - dp0)
              ret[i] = dp[arg] - dp0[arg] + i + 1
  
          if i % 1000 == 999:
              m = 0
              prev = dp[0]
              for k in range(1, dp.shape[0]):
                  if dp[k] > prev:
                      dp0[m] = dp0[k - 1]
                      dp[m] = prev
                      m += 1
                      prev = dp[k]
              else:
                  dp0[m] = dp0[dp0.shape[0] - 1]
                  dp[m] = prev
                  m += 1
              dp0 = dp0[:m]
              dp = dp[:m]
              if arg0 > -1:
                  for j in range(m - 1, -1, -1):
                      if dp[j] == dp0[j]:
                          arg0 = j
                          break
              else:
                  arg = np.argmin(dp - dp0)
      return ret
  
  
  def main(in_file):
      stdin = open(in_file)
      H, W = [int(x) for x in stdin.readline().split()]
      ab = np.fromstring(stdin.read(), i8, sep=" ").reshape((-1, 2)).T
      ans = solve(ab[0] - 1, ab[1].copy(), H, W)
      p = "\n".join([str(x) for x in ans.tolist()])
      print(p)
  
  
  if __name__ == "__main__":
      main("/dev/stdin")
  
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."}]