配点: $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$

出力

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

2 3
1 32
2 63
1 12

000001000002
000002000001
000001000001

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

2 3
2 55
2 77
2 99

000002000001
000002000002
000002000003