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
  
  
  def input():
      return sys.stdin.buffer.readline()[:-1]
  
  
  Q, N = map(int, input().split())
  N += 1
  INF = 10**12
  # N: 処理する区間の長さ
  LV = (N - 1).bit_length()
  N0 = 2**LV
  data = [0] * (2 * N0)
  lazy = [None] * (2 * N0)
  
  
  def gindex(l, r):
      L = (l + N0) >> 1
      R = (r + N0) >> 1
      lc = 0 if l & 1 else (L & -L).bit_length()
      rc = 0 if r & 1 else (R & -R).bit_length()
      for i in range(LV):
          if rc <= i:
              yield R
          if L < R and lc <= i:
              yield L
          L >>= 1
          R >>= 1
  
  
  # 遅延伝搬処理
  def propagates(*ids):
      for i in reversed(ids):
          v = lazy[i - 1]
          if v is None:
              continue
          lazy[2 * i - 1] = lazy[2 * i] = data[2 * i - 1] = data[2 * i] = v >> 1
          lazy[i - 1] = None
  
  
  # 区間[l, r)をxに更新
  def update(l, r, x):
      (*ids,) = gindex(l, r)
      propagates(*ids)
  
      L = N0 + l
      R = N0 + r
      v = x
      while L < R:
          if R & 1:
              R -= 1
              lazy[R - 1] = data[R - 1] = v
          if L & 1:
              lazy[L - 1] = data[L - 1] = v
              L += 1
          L >>= 1
          R >>= 1
          v <<= 1
      for i in ids:
          data[i - 1] = data[2 * i - 1] + data[2 * i]
  
  
  # 区間[l, r)内の合計を求める
  def query(l, r):
      propagates(*gindex(l, r))
      L = N0 + l
      R = N0 + r
  
      s = 0
      while L < R:
          if R & 1:
              R -= 1
              s += data[R - 1]
          if L & 1:
              s += data[L - 1]
              L += 1
          L >>= 1
          R >>= 1
      return s
  
  
  def access(x):
      return query(x, x + 1)
  
  
  lm = 0
  update(0, 1, -INF)
  update(N, N + 1, INF)
  for q in range(1, Q + 1):
      a, b = map(int, input().split())
      a, b = a - 1, b - 1
      if a == lm:
          lm = b + 1
      update(b + 1, b + 2, access(b + 1) + query(a, b + 1) - (b + 1 - a))
      update(a, b + 1, 1)
      res = min(query(0, lm + 1), query(0, max(a, 1)), query(0, b + 1))
      res += INF
      if res > 10**10:
          print(-1)
      else:
          print(res + q)
  
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."}]