{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE CPP                   #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE OverloadedStrings     #-}
{-# LANGUAGE RecordWildCards       #-}
{-# LANGUAGE TupleSections         #-}
{-# LANGUAGE TypeFamilies          #-}

import           Control.Applicative
import           Control.Monad
import           Control.Monad.Primitive
import           Control.Monad.ST
import           Control.Monad.State.Strict
import           Data.Bool
import qualified Data.ByteString.Char8       as B
import qualified Data.ByteString.Unsafe      as B
import           Data.Char
import           Data.Function
import qualified Data.IntMap.Strict          as IM
import qualified Data.IntSet                 as IS
import           Data.List
import qualified Data.Map.Strict             as M
import           Data.Monoid
import           Data.Ord
import           Data.Primitive.MutVar
import qualified Data.Set                    as S
import           Data.Tuple
import qualified Data.Vector                 as V
import qualified Data.Vector.Generic         as G
import qualified Data.Vector.Generic.Mutable as GM
import qualified Data.Vector.Unboxed         as U
import qualified Data.Vector.Unboxed.Mutable as UM
import           Debug.Trace
import           Foreign                     hiding (void)
import           Foreign.C.String
import           Text.Printf
import           Unsafe.Coerce

main :: IO ()
main = do
    [n, m] <- map read.words <$> getLine :: IO [Int]
    pys <- unfoldr parseInt2 <$> B.getContents
    solve pys

solve :: [(Int, Int)] -> IO ()
solve pys = putInts
    . map snd
    . sort
    . concat
    . IM.elems
    . IM.mapWithKey (\p yis -> map (\(j, (_, i)) -> (i, (p, j))) . zip [1 :: Int ..] $ sort yis)
    . foldl' (\acc (i, (p, y)) -> IM.insertWith (++) p [(y, i)] acc) IM.empty
    $ zip [0 :: Int ..] pys

show06d :: Int -> Int -> String
show06d x y = printf "%06d%06d" x y

foreign import ccall unsafe "stdio.h printf"
    c_printf :: CString -> Int -> Int -> IO ()

putInts :: [(Int, Int)] -> IO ()
putInts xs = B.unsafeUseAsCString "%06d%06d\n" $ \fmt ->
    foldr ((>>).uncurry (c_printf fmt)) (return ()) xs

-------------------------------------------------------------------------------
type Parser a = B.ByteString -> Maybe (a, B.ByteString)

parseInt :: Parser Int
parseInt = B.readInt . B.dropWhile isSpace

parseInt2 :: Parser (Int, Int)
parseInt2 = runStateT $
    (,) <$> StateT (B.readInt . B.dropWhile isSpace)
        <*> StateT (B.readInt . B.unsafeTail)

