题目描述

一个大陆上有许多国家，其中$A$国有 $n$ 个市， $m$ 个县，你在国家规划局工作，有一个档案，每条记录告诉你第 $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

样例输入 #1

2 3
1 32
2 63
1 12

样例输出 #1

000001000002
000002000001
000001000001

样例 #2

样例输入 #2

2 3
2 55
2 77
2 99

样例输出 #2

000002000001
000002000002
000002000003

提示

对于 $100\%$ 的数据：

• $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$ 不相同
• 所有的输入都是整数