C - ID

得分: $300$ 分

问题描述

在 Atcoder 共和国，有 $N$ 个州，共有 $M$ 个属于这些州的城市。

第 $i$ 个城市成立于 $Y_i$ 年，并属于第 $P_i$ 个州。

你可以假设没有多个城市在同一年成立。

决定为每个城市分配一个 12 位数的 ID 号码。

如果第 $i$ 个城市是属于第 $i$ 个州的城市中第 $x$ 个成立的城市，那么城市 $i$ 的 ID 号码的前六位是 $P_i$，后六位是 $x$。

在此，如果 $P_i$ 或 $x$（或两者都）的位数不足六位数，则在左侧填充零，直到达到六位数。

找出所有城市的 ID 号码。

请注意，可能存在没有城市的州。

约束

• $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$

输出

以索引升序（城市 $1$，城市 $2$，$...$）打印所有城市的 ID 号码。

2 3
1 32
2 63
1 12

000001000002
000002000001
000001000001

• City $1$ 是属于州 $1$ 的城市中第 $2$ 个成立的城市，其 ID 号码为 $000001000002$。
• City $2$ 是属于州 $2$ 的城市中第 $1$ 个成立的城市，其 ID 号码为 $000002000001$。
• City $3$ 是属于州 $1$ 的城市中第 $1$ 个成立的城市，其 ID 号码为 $000001000001$。

2 3
2 55
2 77
2 99

000002000001
000002000002
000002000003