input = require('fs').readFileSync('/dev/stdin', 'utf8')
lines = input.split('\n')
lines.shift()
lines.pop()
l = lines.map((x, i) => {
    a = x.split(' ').map(x => x * 1)
    a.i = i
    return a
}).sort((a, b) => {
  return a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]
})

arr = []
y = ''
for (i=0; i<l.length; i++) {
    if (y != l[i][0]) {
        j = 1 
        y = l[i][0]
    }
    arr[l[i].i] = ('000000' + l[i][0]).slice(-6) + ('000000' + j).slice(-6)
    j++
}
console.log(arr.join('\n'))