题目描述

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$

输出格式

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

题目大意

注：由于日本与我国行政区划单位的区别，翻译时有改动。

$A$ 国有 $M$ 个县和 $N$ 个市，第 $i$ 个县属于第 $P_i$ 个市，建立的年份为 $Y_i$。现在想要分给每个县一个由 $12$ 位数字组成的编号，如果第 $i$ 个县属于第 $P_i$ 个市且是第 $x$ 个创立的，则该县编号前六位为 $P_i$，后六位为 $x$ 。试求出所有县的编号并按输入顺序输出。

注：若 $P_i,x$ 的位数不到六位则在前面补 $0$ ，有的市可能一个县都没有。

2 3
1 32
2 63
1 12

000001000002
000002000001
000001000001

2 3
2 55
2 77
2 99

000002000001
000002000002
000002000003

提示

制約

• $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$ となります。