题目描述

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.

阿特科德共和国有 $N$ 个县，这些县共有 $M$ 个市。

城市 $i$ 建于 $Y_i$ 年，隶属于 $P_i$ 县。

可以认为没有多个城市在同一年建立。

我们决定为每个城市分配一个 $12$ 位数的身份证号码。

如果城市 $i$ 是隶属于县 $i$ 的城市中第 $x$ 个建立的城市，那么城市 $i$ 的身份证号码的前六位是 $P_i$ ，后六位是 $x$ 。

在此，如果 $P_i$ 或 $x$ ｝(或两者都少于六位数，则在左边添加零，直到六位数为止。

找出所有城市的身份证号码。

请注意，可能存在没有城市的都道府县。

输入格式

输入内容按以下格式标准输入：

$N$ $M$
$P_1$ $Y_1$
$:$
$P_M$ $Y_M$

输出格式

按指数升序打印所有城市的 ID 编号（城市 $1$ 、城市 $2$ 、 $...$ ）。

样例 #1

样例输入 #1

2 3
1 32
2 63
1 12

样例输出 #1

000001000002
000002000001
000001000001

样例 #2

样例输入 #2

2 3
2 55
2 77
2 99

样例输出 #2

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$ 都是不同的。
• 输入值均为整数。

样例 $1$ 解释

• 由于城市 $1$ 是隶属于县 $1$ 的第二个建制市，因此其 ID 编号为 $000001000002$ 。
• 由于 $2$ 市是 $2$ 县所属城市中的第一个建制市，其身份证号码为 $000002000001$ 。
• 由于 $3$ 市是 $1$ 县所属城市中的第一个建制市，其身份证号码为 $000001000001$ 。