AT_abc113_c [ABC113C] ID

[problemUrl]: https://atcoder.jp/contests/abc113/tasks/abc113_c 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 $ つも属さない県がある場合に注意してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ P_1 $ $ Y_1 $ $ : $ $ P_M $ $ Y_M $

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

### 制約 - $ 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 $ は全て異なる - 入力は全て整数 ### Sample Explanation 1 \- 市 $ 1 $ は県 $ 1 $ に属する市の中で $ 2 $ 番目に誕生したので、認識番号は $ 000001000002 $ となります。 - 市 $ 2 $ は県 $ 2 $ に属する市の中で $ 1 $ 番目に誕生したので、認識番号は $ 000002000001 $ となります。 - 市 $ 3 $ は県 $ 1 $ に属する市の中で $ 1 $ 番目に誕生したので、認識番号は $ 000001000001 $ となります。