program main
implicit None
	integer(8)::n,m,i,j,q,r
	integer(8),allocatable::p(:),y(:),a(:),b(:),c(:)
	
	read*,n,m
	allocate(p(m),y(m),a(m),b(m))
	
	do i = 1,m
		read*,p(i),y(i)
		a(i) = i
	enddo
	
	b = p
	call h2(p,a,m)
	p = b
	call h2(p,y,m)
	deallocate(b)
	
	q = 1
	r = 1
	
	do
		do
			if(r+1 > m)exit
			if(p(r+1)/=p(r))exit
			r = r+1
		enddo
		j = r-q+1
		allocate(b(j),c(j))
		b(1:j) = y(q:r)
		c(1:j) = a(q:r)
		call h2(b,c,j)
		do i = 1,j
			b(i) = i
		enddo
		y(q:r) = b(1:j)
		a(q:r) = c(1:j)
		q = r+1
		r = r+1
		deallocate(b,c)
		if(r+1>m)exit
	enddo
	
!	do i = 1,m
!	print *,p(i),y(i),a(i)
!	enddo
	
	allocate(b(m))
	b = a
	call h2(a,p,m)
	a = b
	call h2(a,y,m)
	
	do i = 1,m
		y(i) = p(i)*1000000+y(i)
	enddo
	
	do i = 1,m
	print"(i12.12)",y(i)
	enddo
	
end program main


subroutine h2(a,b,n)
implicit None
	integer(8)::a(n),b(n),x,y
	integer(8)::n,i,ie,i0,i1,i2
	
	do i = n/2,1,-1
		x = a(i);y = b(i);ie = n + 1; i0 = i; i1 = i0 * 2
		do while(i1 < ie)
			i2 = i1 + 1
			if(i2 < ie .and. a(i1) < a(i2)) i1 = i2
			if(a(i1) > x)then
				a(i0) = a(i1);a(i1) = x
				b(i0) = b(i1);b(i1) = y
				else
				exit
			endif
			i0 = i1;i1 = i0 *2
		enddo
	enddo
	do ie = n,2,-1
		x = a(ie);y = b(ie)
		a(ie) = a(1);b(ie) = b(1)
		a(1) = x;b(1) = y
		i0 =1;i1 =2
		do while(i1 <ie)
			i2 = i1 +1
			if(i2 < ie .and. a(i1) < a(i2)) i1 = i2
			if(a(i1) > x)then
				a(i0) = a(i1);a(i1) = x
				b(i0) = b(i1);b(i1) = y
				else
				exit
			endif
			i0 = i1;i1 = i0 *2
		enddo
	enddo
end subroutine h2