import qualified Data.ByteString.Char8 as BS
import Data.List
import Control.Monad
main=do
 [n,m]<-map read.words<$>getLine
 py<-replicateM m (map (read.BS.unpack).BS.words<$>BS.getLine)
 mapM_ putStrLn (h m (sort(g m 0 0 (sort(f m m py)))))
  where f _ 0 l =[]
        f m n (x:l) =(x++[m-n]):(f m (n-1) l)
        g 0 _ _ pyi =[]
        g m j n ([p,y,i]:pyi) |p==j =[i,p,n+1]:(g (m-1) j (n+1) pyi)
                              |p>j  =[i,p,1]:(g (m-1) p 1 pyi)
        h 0 ipy =[]
        h m ([i,p,y]:ipy) =((k(show p))++(k(show y))):(h (m-1) ipy)
        k n =(take(6-(length n))(repeat '0'))++n