local mmi, mma = math.min, math.max
local h, w = io.read("*n", "*n")
local a, b = {}, {}
for i = 1, h do
  a[i], b[i] = io.read("*n", "*n")
end
if a[1] == 1 and b[1] == w then
  for i = 1, h do
    print(-1)
  end
  os.exit()
end

local asked_by_depth = {}
for i = 1, h do
  asked_by_depth[i] = {}
end
local inf = 1000000007
local ret = {}
for i = 1, h + 1 do
  ret[i] = inf
end
local task_l, task_r, task_len, task_d = {}, {}, {}, {}
local function addtask(left, right, curlen, deg)
  table.insert(task_l, left)
  table.insert(task_r, right)
  table.insert(task_len, curlen)
  table.insert(task_d, deg)
end

local function solve(left, right, curlen, deg)
  deg = deg + 1
  if h < deg then return end
  curlen = curlen + 1
  if a[deg] <= left and right <= b[deg] then
    if b[deg] == w then return end
    curlen = curlen + b[deg] + 1 - right
    ret[deg] = mmi(ret[deg], curlen)
    addtask(b[deg] + 1, b[deg] + 1, curlen, deg)
  elseif right < a[deg] or b[deg] < left then
    ret[deg] = mmi(ret[deg], curlen)
    addtask(left, right, curlen, deg)
  elseif b[deg] < right then
    ret[deg] = mmi(ret[deg], curlen)
    if a[deg] < left then
      addtask(left, a[deg] - 1, curlen, deg)
    end
    addtask(b[deg] + 1, right, curlen, deg)
  elseif left < a[deg] then
    ret[deg] = mmi(ret[deg], curlen)
    addtask(left, a[deg] - 1, curlen, deg)
  end
end

if 1 < a[1] then
  addtask(1, a[1] - 1, 0, 0)
end
if b[1] < w then
  addtask(b[1] + 1, w, 0, 0)
end
while 0 < #task_l do
  local left = task_l[#task_l]
  table.remove(task_l)
  local right = task_r[#task_r]
  table.remove(task_r)
  local curlen = task_len[#task_len]
  table.remove(task_len)
  local deg = task_d[#task_d]
  table.remove(task_d)
  solve(left, right, curlen, deg)
end
for i = 1, h do
  if ret[i] == inf then ret[i] = -1 end
end
ret[h + 1] = nil
print(table.concat(ret, "\n"))
