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 hsort(a,n)
implicit None
	integer(8)::a(n),x
	integer(8)::n,i,k,i0,c1,c2
	
	do i = n/2,1,-1
		x = a(i);k = n + 1; i0 = i; c1 = i0 * 2
		do while(c1 < k)
			c2 = c1 + 1
			if(c2 < k .and. a(c1) < a(c2)) c1 = c2
			if(a(c1) > x)then
				a(i0) = a(c1);a(c1) = x
				else
				exit
			endif
			i0 = c1;c1 = i0 *2
		enddo
	enddo
	do k = n,2,-1
		x = a(k)
		a(k) = a(1)
		a(1) = x
		i0 =1;c1 =2
		do while(c1 <k)
			c2 = c1 +1
			if(c2 < k .and. a(c1) < a(c2)) c1 = c2
			if(a(c1) > x)then
				a(i0) = a(c1);a(c1) = x
				else
				exit
			endif
			i0 = c1;c1 = i0 *2
		enddo
	enddo
end subroutine hsort