ID

题目描述

在 Atcoder 共和国，有 $N$ 个县（prefectures），一共有 $M$ 个属于这些县的城市。 城市 $i$ 建立于年份 $Y_i$ 并且属于县 $P_i$。 可以假定不存在在同一年建立的多个城市。 决定为每个城市分配一个 12 位的 ID 号码。 如果城市 $i$ 在属于县 $P_i$ 的城市中是第 $x$ 个建立的城市，则城市 $i$ 的 ID 号码的前六位是 $P_i$，后六位是 $x$。 这里，如果 $P_i$ 或 $x$（或两者）少于六位数，则在左侧补零直到它有六位。 求所有城市的 ID 号码。 注意可能存在没有城市的县。

输入格式

输入从标准输入按以下格式给出： $N$ $M$ $P_1$ $Y_1$ : $P_M$ $Y_M$

输出格式

按城市索引的升序（城市 $1$、城市 $2$、……）打印所有城市的 ID 号码。

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$ 都不相同。 输入中的所有数值都是整数。由于城市 $1$ 在属于县 $1$ 的城市中是第 2 个建立的城市，它的 ID 号码是 $000001000002$。 由于城市 $2$ 在属于县 $2$ 的城市中是第 1 个建立的城市，它的 ID 号码是 $000002000001$。 由于城市 $3$ 在属于县 $1$ 的城市中是第 1 个建立的城市，它的 ID 号码是 $000001000001$。

标签: AtCoder|abc113C

来源

AtCoder|abc113C