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

local inf = 1000000007
local ret = {}
for i = 1, h do
  ret[i] = inf
end
local task_l, task_r, task_len, task_d = {}, {}, {}, {}
local function addtask(left, right, curlen, deg)
  ret[deg] = mmi(ret[deg], curlen)
  table.insert(task_l, left)
  table.insert(task_r, right)
  table.insert(task_len, curlen)
  table.insert(task_d, deg)
end
local function addtask_start(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
    addtask(b[deg] + 1, b[deg] + 1, curlen, deg)
  elseif right < a[deg] or b[deg] < left then
    addtask(left, right, curlen, deg)
  else
    if b[deg] < right then
      addtask(b[deg] + 1, right, curlen, deg)
    elseif b[deg] < w then
      curlen = curlen + b[deg] + 1 - right
      addtask(b[deg] + 1, b[deg] + 1, curlen, deg)
    end
    if left < a[deg] then
      addtask(left, a[deg] - 1, curlen, deg)
    end
  end
end
addtask_start(1, w, 0, 0)
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
print(table.concat(ret, "\n"))
