import GHC.Exts
import Data.Map (Map,(!))
import qualified Data.Map as M
import Control.Monad

main = do
  [n,m] <- map read.words <$> getLine
  dat <- zip [1..].map ((\[a,b]->(a,b)).map read.words) <$> replicateM m getLine
  let ls = M.elems.M.fromList.concatMap (to1nSndSnd.sortWith (snd.snd)).groupWith (fst.snd) $ sortWith (fst.snd) dat
  forM_ ls $ \(a,b) -> putStr (conv 6 a) >> putStrLn (conv 6 b)

to1nSndSnd :: [(a,(b,c))] -> [(a,(b,Int))]
to1nSndSnd = inner 1
  where
  inner _ [] = []
  inner i ((a,(b,_)):xs) = (a,(b,i)) : inner (i+1) xs

conv :: Int -> Int -> String
conv n a = replicate (n-length s) '0' ++ s
  where s = show a