题目描述

$A$ 国有 $M$ 个县和 $N$ 个市，第 $i$ 个县属于第 $P_i$ 个市，建立的年份为 $Y_i$。现在想要分给每个县一个由 $12$ 位数字组成的编号，如果第 $i$ 个县属于第 $P_i$ 个市且是第 $x$ 个创立的，则该县编号前六位为 $P_i$，后六位为 $x$ 。试求出所有县的编号并按输入顺序输出。

注：若 $P_i,x$ 的位数不到六位则在前面补 $0$ ，有的市可能一个县都没有。

输入格式

第一行两个整数 $N, M$。

接下来 $M$ 行，每行两个整数 $P_i, Y_i$。

$1 \le N, M \le 10^5$，$1 \le P_i \le N$，$1 \le Y_i \le 10^9$。数据保证 $Y_i$ 不同。

输出格式

按照城市递增的顺序输出每个城市的 ID。

2 3
1 32
2 63
1 12

000001000002
000002000001
000001000001

2 3
2 55
2 77
2 99

000002000001
000002000002
000002000003