← 返回题目列表

AtCoder · abc113_c

C. 身份编号

中文机器翻译题面 查看原题

分数: 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