题目描述

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

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

可以假设不存在在同一年建立的多个城市。

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

如果第 $i$ 个城市是第 $P_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 号码。

示例输入 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