const input = require("fs").readFileSync("/dev/stdin", "utf8")

;(input => {
    const lines = input.split('\n')
    const [N, M] = lines[0].split(' ').map(Number)

    const C = []
    for (let i = 0; i < M; i++) {
    C[i] = [...lines[i + 1].split(' ').map(Number), i]
    }

    C.sort((a, b) => {
        if (a[0] === b[0]) {
            return a[1] > b[1] ? 1 : -1
        } else {
            return a[0] > b[0] ? 1 : -1
        }
    })

    let ans = []
    let p = 0
    let x = 0
    for (let i = 0; i < M; i++) {
        if (p === C[i][0]) {
            x ++
        } else {
            p = C[i][0]
            x = 1
        }
        ans.push([
            ( '000000' + C[i][0] ).slice( -6 ) +
            ( '000000' + x ).slice( -6 ),
            C[i][2]
        ])
    }

    ans.sort((a, b) => {
        return a[1] > b[1] ? 1 : -1
    })

    for (let i = 0; i < M; i++) {
        ans[i] = ans[i][0]
    }

    console.log(ans.join('\n'))

})(input)
