while(m,n=gets.split.map &:to_i)[0]>t=0
l=(1..n).map{|i|[i,gets.to_i]}
a=[]
s=(1..m).map{[]}
until a[n-1]
t+=1
s.map{|d|a<<d.pop[0]while d[0]&&d[-1][1]<=t}
(x,y=l.shift
i=y+=t
s.min_by{|d|i+=1;d[1]?[1e9]:d[0]?[1,(y<(e=d[0][1])?(e-y):1e9),y-e,i]:[0,i]}<<[x,y])while l[0]&&l[0][0]*10<t&&!s.all?{|d|d[1]}end
puts a*" "end