H,W = gets.split.map(&:to_i)

r = *0..W
r[0] = 1 # 0 は欠番
nmin = [0]*W
nmin[rmin=0] = W
puts $<.map.with_index(1){|ln,k|
	next -1 if rmin < 0
	a,b = ln.split.map(&:to_i)

	i,c = a
	until b < i
		j = r[i]
		if i < j
			i = j
		else
			c = j
			nmin[i-c] -= 1
			i += 1
		end
	end
	if c && b<W
		rb = r[b+1]
		nmin[b+1-rb] -= 1 if rb<c
		if b+1 < rb || rb < c
			r[b+1] = c
			nmin[b+1-c] += 1
		end
	end
	r.fill(b+1,a..b)

	rmin = (rmin...W).find{|v| 0<nmin[v] }||~k
	next k+rmin
}
