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

優 = [-1]*(H+1)
経 = [W]*(H+1)
h = 0 # 0..H

AB << [0,0] # AB[-1]
経 << 1 # 経[-1]
経[0] += 1

while 0 <= h
	経[h] -= 1
	next h-=1 if h == H

	l,a,b = 経[h-1],*AB[h-1]
	経[h] = a-1 if (a..b).include? 経[h]
	next h-=1 unless l <= 経[h]

	優？ = h+経[h]-経[0]
	優[h] = 優？ if 優[h] == -1 or 優？ < 優[h]
	next if 経[h+1] < 経[h]

	next 経[h+=1]+=1
end

puts 優.drop(1)
