'use strict'

const main = input => {
	const args = input.split('\n').map(arg => arg.split(' '))
	const N = parseInt(args[0][0], 10)
	const M = parseInt(args[0][1], 10)
	let A = new Array()

	for (let i = 0; i < M; i++) {
		A.push({
			i: i,
			p: parseInt(args[i + 1][0], 10),
			y: parseInt(args[i + 1][1], 10),
			n: null
		})
	}

	for (let i = 0; i < M; i++) {
		A.filter(t => t.p === i).sort((a, b) => a.y - b.y).forEach((t, _i) => {
			t.n = _i + 1
		})
	}

	for (let i = 0; i < M; i++) {
		console.log(`${('000000' + A[i].p).slice(-6)}${('000000' + A[i].n).slice(-6)}`)
	}
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'))
