(H,W),*AB = $<.map{|ln| ln.split.map(&:to_i) }

r = (1..W).map{|c| [c,0] }
AB.each.with_index(1){|(a,b),k|
	i = (0...r.size).bsearch{|i| a<=r[i][0] }||r.size
	j = (0...r.size).bsearch{|j| b< r[j][0] }||r.size
	l = r[j] && b+1 == r[j][0] ? j : j-1 if i<j && b<W
	r.insert(j,[b+1,r[l][1]+b+1-r[l][0]]) if l
	r.slice! i...j
	p(r.empty? ? -1 : k+r.min_by{|_,v| v }[1])
}
