{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE BinaryLiterals #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE NumDecimals #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TupleSections #-}

import Control.Applicative
import Control.Arrow
import Control.Monad
import Control.Monad.ST

import Data.Char
import Data.List
import Data.Maybe

import qualified Data.ByteString.Char8 as B

import Data.Array.ST.Safe
import Data.STRef

import Debug.Trace
import Text.Printf

readInt = readLn :: IO Int
readInts = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine
readNInts = readInt >>= flip replicateM readInt

which a b f = if f then a else b
mp [ a, b ] = ( a, b )

modifyArray a i f = writeArray a i =<< f <$> readArray a i

main = do
	[ n, m ] <- readInts
	[ ps, ys ] <- transpose <$> replicateM m readInts
	mapM_ ( uncurry $ printf "%06d%06d\n" ) $ solve n ( sort $ zip3 ys ( map pred ps ) [ 0 .. ] )

solve n lists = runST $ do
	counts <- newArray ( 0, n ) 0 :: ST s ( STUArray s Int Int )
	res <- newArray_ ( 0, n ) :: ST s ( STArray s Int ( Int, Int ) )
	forM_ lists $ \( y, p, idx ) -> do
		modifyArray counts p succ
		nth <- readArray counts p
		writeArray res idx ( p + 1, nth )
	getElems res