console.log((args=>{
  const [[N,M],...tmp] = args.trim().split('\n').map( r=>r.split(' ').map(v=>v|0) );
  const p = Array.from({length:N},_=>[]);
  for ( let i = 0; i < M; i++ ) {
    const [P,Y] = tmp[i];
    p[P-1].push([i,Y]);
  }
  p.forEach(r=>r.sort((a,b)=>a[1]-b[1]));
  const a = Array.from(tmp,([p])=>`${p}`.padStart(6,0));
  p.forEach(r=>r.forEach(([i],j)=>a[i] += `${j+1}`.padStart(6,0)))
  return a.join`\n`;
})(require('fs').readFileSync('/dev/stdin', 'utf8')));
