n,m=gets.split.map &:to_i
data=[]
shi=[]
n.times{shi<<[]}
m.times {
    d=gets.split.map(&:to_i)
    data << d
    shi[d[0]-1] << d[1]

}
shi.each{|e|e.sort!}
data.each{|d|
    printf("%06d%06d\n",d[0],shi[d[0]-1].index(d[1])+1)
}