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

r = (1..W).map{|c| [0,c] }
nmin = [0]*W
nmin[rmin=0] = W
puts AB.map.with_index(1){|(a,b),k|
	i = (0...r.size).bsearch{|i| a<=r[i][1] }||r.size
	j = (i...r.size).bsearch{|j| b< r[j][1] }||r.size
	u = r[j] && b+1 == r[j][1] ? j : j-1 if i<j && b<W
	v = r[u][0] + b+1 - r[u][1] if u

	(i...j).each{|i| nmin[r[i][0]]-=1 }
	nmin[v] += 1 if v
	r[i...j] = v ? [[v,b+1]] : []
	rmin = r.empty? ? ~k : (rmin...W).find{|v| 0<nmin[v] }

	next k+rmin
}
