C - ID 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点: 300 点

問題文

Atcoder国には N 個の県があり、これらの県には合計で M 個の市が属しています。

市 i が誕生したのは Y_i 年であり、県 P_i に属しています。

ただし、同じ年に誕生した市が複数存在することはないとします。

それぞれの市に 12 桁の認識番号を割り振ることとなりました。

市 i が 県 P_i に属する市の中で x 番目に誕生した市のとき、市 i の認識番号の上 6 桁は P_i、下 6 桁は x となります。

ただし、P_i や x が 6 桁に満たない場合は 6 桁になるまで 0 を左に追加するものとします。

全ての市の認識番号を求めてください。

ただし、市が 1 つも属さない県がある場合に注意してください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq P_i \leq N
  • 1 \leq Y_i \leq 10^9
  • Y_i は全て異なる
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M
P_1 Y_1
:
P_M Y_M

出力

全ての市の認識番号を市の番号の昇順に出力せよ。

入力例 1

2 3
1 32
2 63
1 12

出力例 1

000001000002
000002000001
000001000001
  • 市 1 は県 1 に属する市の中で 2 番目に誕生したので、認識番号は 000001000002 となります。
  • 市 2 は県 2 に属する市の中で 1 番目に誕生したので、認識番号は 000002000001 となります。
  • 市 3 は県 1 に属する市の中で 1 番目に誕生したので、認識番号は 000001000001 となります。

入力例 2

2 3
2 55
2 77
2 99

出力例 2

000002000001
000002000002
000002000003

Score: 300 points

Problem Statement

In Republic of Atcoder, there are N prefectures, and a total of M cities that belong to those prefectures.

City i is established in year Y_i and belongs to Prefecture P_i.

You can assume that there are no multiple cities that are established in the same year.

It is decided to allocate a 12-digit ID number to each city.

If City i is the x-th established city among the cities that belong to Prefecture i, the first six digits of the ID number of City i is P_i, and the last six digits of the ID number is x.

Here, if P_i or x (or both) has less than six digits, zeros are added to the left until it has six digits.

Find the ID numbers for all the cities.

Note that there can be a prefecture with no cities.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq P_i \leq N
  • 1 \leq Y_i \leq 10^9
  • Y_i are all different.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
P_1 Y_1
:
P_M Y_M

Output

Print the ID numbers for all the cities, in ascending order of indices (City 1, City 2, ...).

Sample Input 1

2 3
1 32
2 63
1 12

Sample Output 1

000001000002
000002000001
000001000001
  • As City 1 is the second established city among the cities that belong to Prefecture 1, its ID number is 000001000002.
  • As City 2 is the first established city among the cities that belong to Prefecture 2, its ID number is 000002000001.
  • As City 3 is the first established city among the cities that belong to Prefecture 1, its ID number is 000001000001.

Sample Input 2

2 3
2 55
2 77
2 99

Sample Output 2

000002000001
000002000002
000002000003