分数: 300 点
问题陈述
在 Atcoder 共和国中,有 N 都道府县,总共 M 属于这些都道府县的城市。
城市 i 成立于 年 Y_i 属于县 P_i.
您可以假设同一年没有建立多个城市。
决定分配一个 12- 每个城市的数字 ID 号。
如果城市 i 是 x县属城市中第 1 个设立城市 i,城市ID号前六位 i is P_i,身份证号码后六位为 x.
这里,如果 P_i or 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
输出
按索引升序打印所有城市的 ID 号(城市 1, 城市 2, ...).
示例输入 1
2 3 1 32 2 63 1 12
示例输出 1
000001000002 000002000001 000001000001
- 作为城市 1 是地属城市中第二个设立的城市 1,其 ID 号为 000001000002.
- 作为城市 2 是地属城市中第一个设立的城市 2,其 ID 号为 000002000001.
- 作为城市 3 是地属城市中第一个设立的城市 1,其 ID 号为 000001000001.
示例输入 2
2 3 2 55 2 77 2 99
示例输出 2
000002000001 000002000002 000002000003