某国有 N 个县，编号 1 \sim N；共有 M 个城市，编号 1 \sim M。第 i 个城市属于 P_i 号县，并且建于 Y_i 年。所有 Y_i **两两不同**（没有两个城市同年建立）。

每个城市都要分配一个长度恰好为 12 的数字串编号，规则是：

- **前 6 位**：该城市所属的县编号，不足 6 位时**在左边补 0**；

- **后 6 位**：在该城市所属的县内部，把该县的所有城市**按建市年份从早到晚**排序，这个城市排在第几个就是几，同样不足 6 位在左边补 0。

两部分直接拼起来（中间没有空格、没有分隔符）。

例如：7 号县建于最早的那个城市编号为 `000007000001`，同县第二个建成的城市是 `000007000002`。

请输出编号规则下 M 个城市的编号，**按城市原本的编号 1 \sim M 的顺序**，每行一个。

N M

P_1 Y_1

P_2 Y_2

...

P_M Y_M

M 行，第 i 行是一个长度 12 的数字串，表示城市 i 的编号。

- 1 \le N \le 10^5，1 \le M \le 10^5

- 1 \le P_i \le N

- 1 \le Y_i \le 10^9，且 Y_i 两两不同

- 注意：M 可能远小于 N（很多县一个城市都没有）；也可能所有城市都挤在同一县，在日本，县其实对应的是我们这边的省

| t1 | 10 | N \le 5，M \le 10 | 

| t2 | 20 | N \le 50，M \le 300 |  

| t3 | 30 | N \le 2000，M \le 5000 | 

| t4 | 40 | N, M \le 10^5 |