program main
implicit None
	integer(8)::m,n,i,a
	integer(8),allocatable::p(:),y(:),j(:),d(:),c(:)
	
	read *,n,m
	allocate(p(m),y(m),j(m),d(m),c(n))
	
	do i = 1,m
		read *,p(i),y(i)
	enddo
	
	j = y
	
	call hsort(j,m)
	
	c = 0
	do i = 1,m
		a = 1
		do while(j(i) /= y(a))
			a = a + 1
		enddo
		d(a) = p(a)*1000000 + c(p(a)) + 1
		c(p(a)) = c(p(a)) + 1
	enddo
	
	do i = 1,m
		print 101,d(i)
	enddo
	
101 format(i12.12)
end program main

subroutine makeheap(a,n)
Implicit None
	integer(8)::n,i,c1,c2,p,t,m
	integer(8)::a(n)
	
	do i = n/2,1,-1
		p = i; c1 = i * 2
		do while (c1 <= n)
			c2 = c1 + 1
			if(c2 <= n .and. a(c2) > a(c1)) c1 = c2
			if(a(p) < a(c1))then
				t = a(p)
				a(p) = a(c1)
				a(c1) = t
				p = c1
				c1 = p*2
				else
					exit
			endif
		enddo
	enddo
	
end subroutine makeheap

subroutine hsort(a,n)
Implicit None
	integer(8)::n,t,i,p,c1,c2,j
	integer(8)::a(n)
	
	call makeheap(a,n)
	
	do i = n,2,-1
		t = a(i)
		a(i) = a(1)
		a(1) = t
		
		p = 1
		do
			c1 = p*2
			if (c1 >= i) exit
			
			c2 = c1 +1
			if(c2 < i .and. a(c2) > a(c1))then
					c1 = c2
			endif
			
			if(a(c1) >a(p))then
				t = a(p)
				a(p) = a(c1)
				a(c1) = t
				p = c1
				else
					exit
			endif
		enddo
	enddo
end subroutine hsort