识别编号

题目描述

Atcoder 国有 $N$ 个县,这些县总共下辖 $M$ 个市。

市 $i$ 诞生于 $Y_i$ 年,隶属于县 $P_i$。

注意,不存在同一年诞生的多个市。

现在要为每个市分配一个 $12$ 位的识别编号。

当市 $i$ 是隶属于县 $P_i$ 的所有市中第 $x$ 个诞生的市时,市 $i$ 的识别编号前 $6$ 位为 $P_i$,后 $6$ 位为 $x$。

若 $P_i$ 或 $x$ 不足 $6$ 位,则在左侧补 $0$ 直到满 $6$ 位。

请求出所有市的识别编号。

注意,可能存在没有任何市下辖的县。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

按照市编号的升序输出所有市的识别编号。

样例

2 3
1 32
2 63
1 12

000001000002
000002000001
000001000001

• 市 $1$ 是隶属于县 $1$ 的所有市中第 $2$ 个诞生的,因此识别编号为 $000001000002$。
• 市 $2$ 是隶属于县 $2$ 的所有市中第 $1$ 个诞生的,因此识别编号为 $000002000001$。
• 市 $3$ 是隶属于县 $1$ 的所有市中第 $1$ 个诞生的,因此识别编号为 $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$ 各不相同
• 输入均为整数