某大型企业为了统一管理资产，对设备的采购与编号制定了严格的规则。
该企业下设有 N 个部门。按照公司制度规定，在同一年内最多只能采购一套设备。截至目前，公司一共采购了 M 套设备。
对于第 i 套设备：
保证 不存在两套设备在同一年被采购。
现在公司需要为每一套设备分配一个 12 位的设备编号，编号规则如下：
若某设备是其所属部门中第 x 套被采购的设备（指在该部门中，按采购年份从小到大排序后的第 x 套）， 则该设备编号由两部分组成：
若部门编号 P_i 或顺序编号 x 的位数不足 6 位，则在左侧补 0，直至 6 位。
请你为每一套设备计算并输出对应的设备编号。
需要注意的是：有些部门可能至今尚未采购任何设备。
第 1 行包含两个整数 N 和 M，分别表示部门数和采购设备的数量。
接下来 M 行，每行包含两个整数 P_i 和 Y_i，分别表示第 i 套设备所属部门编号和采购年份。
按照输入中设备的顺序（即第 1 套到第 M 套设备），依次输出每套设备对应的 12 位设备编号，每行一条。
2 3 1 32 2 63 1 12
000001000002 000002000001 000001000001
2 3 2 55 2 77 2 99
000002000001 000002000002 000002000003
4 10 3 254 1 316 2 43 2 91 2 3535 3 2018 4 112 1 1 2 53 4 5235
000003000001 000001000002 000002000001 000002000003 000002000004 000003000002 000004000001 000001000001 000002000002 000004000002
100000 1
50098 314736152
050098000001
000001000002。000002000001。000001000001。三套设备均由部门 2 采购，且采购年份依次递增，因此它们在该部门中的采购顺序分别为第 1、2、3 次。
请注意 Y_i \le 10^9。
对于 100\% 的数据，满足 1 \le N \le 10^5，1 \le M \le 10^5，1 \le P_i \le N，1 \le Y_i \le 10^9，所有 Y_i 互不相同。
| 测试点编号 | N | M |
|---|---|---|
| 1 | =1 | =1 |
| 2 | =1 | =10^5 |
| 3 | =10^5 | =1 |
| 4 | \le 10^5 | \le 1000 |
| 5 | \le 500 | \le 10^5 |
| 6 \sim 10 | \le 10^5 | \le 10^5 |