import Text.Printf
import Data.List
import Data.Maybe
import qualified Data.ByteString.Char8 as B
import qualified Data.IntMap as IM
import qualified Data.Set as S
main=mapM_ putStrLn.solve.map((\[a,b]->(a,b)).map(fst.fromJust.B.readInt).B.words).B.lines=<<B.getContents
solve((n,m):pys)=map(\(p,y)->concatMap(printf"%06d")[p,S.findIndex y(m IM.! p)+1])pys where
  m=foldr(\gs m->IM.insert(fst$gs!!0)(S.fromList$map snd gs)m)IM.empty.groupBy(\a b->fst a==fst b).sort$pys