题目描述

有 $N$ 个地区和 $M$ 座城市。城市 $i$ 属于地区 $P_i$，建立年份为 $Y_i$，所有城市年份互不相同。将每个地区内的城市按年份升序排名，从 1 开始。城市识别码为六位地区编号与六位地区内排名的拼接，每部分不足六位时左侧补零。按城市输入顺序输出识别码。

输入格式

第一行 $N$、$M$；随后 $M$ 行，每行两个整数 $P_i$、$Y_i$。

输出格式

输出 $M$ 行，每行一个恰好十二位的识别码，顺序与输入城市顺序相同。

数据范围

$1 \le N,M \le 10^{5}$；$1 \le P_i \le N$；$1 \le Y_i \le 10^{9}$；所有年份全局互异。允许有地区没有城市。

输入输出样例

样例 1

1 1
1 1

000001000001

样例 2

100000 1
100000 1000000000

100000000001

样例 3

1 3
1 90
1 60
1 10

000001000003
000001000002
000001000001

样例 4

3 4
2 80
1 30
2 20
3 10

000002000002
000001000001
000002000001
000003000001

样例 5

5 3
5 1
1 2
5 3

000005000001
000001000001
000005000002

样例 6

2 4
1 1000000000
2 1
1 2
2 999999999

000001000002
000002000001
000001000001
000002000002

样例 7

1 12
1 12
1 11
1 10
1 9
1 8
1 7
1 6
1 5
1 4
1 3
1 2
1 1

000001000012
000001000011
000001000010
000001000009
000001000008
000001000007
000001000006
000001000005
000001000004
000001000003
000001000002
000001000001