def min(a,b); a < b ? a : b; end
def max(a,b); a > b ? a : b; end
  
INF = 1 << 28
H, W = gets.split.map(&:to_i)
T = {}
(1 .. W).each{|x| T[x] = x }

ans = (1 .. H).map do |y|
  a, b = gets.split.map(&:to_i)

  removed_keys = []
  removed_max_value = -1
  min_move = 2 * INF
  
  T.each do |k, v|
    if a <= k && k <= b
      removed_keys << k
      removed_max_value = max(removed_max_value, v)
    elsif k <= W
      min_move = min(k - v + y, min_move)
    end
  end
  
  if removed_keys.size > 0
    removed_keys.each{|k| T.delete(k) }
    if T[b + 1]
      T[b + 1] = max( T[b + 1], removed_max_value)
    else
      T[b + 1] = removed_max_value
    end
    min_move = min(y + b + 1 - T[b + 1], min_move) if b + 1 <= W
  end
  min_move >= INF ? -1 : min_move
end
puts ans