题目描述

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

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

你可以假设没有多个城市在同一年成立。

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

如果第$i$个城市是属于第$i$个州的城市中第$x$个成立的城市，那么城市$i$的 ID 号码的前六位是$P_i$;后六位是$x$。

在此，如果$P_i$ 或 $x$ 的位数不足六位数，则在左侧填充零，直到达到六位数。 找出所有城市的 ID 号码。 请注意，可能存在没有城市的州。

输入

第一行两个整数分别表述州的数目和城市的数目

接下来每行两个整数分别表示第$i$个城市属于的州$p_i$和对应的城市成立的年份$y_i$

输出

按照输入顺序打印所有城市的ID号码

2 3
1 32
2 63
1 12

000001000002
000002000001
000001000001

样例解释

City 1 是属于州 1 的城市中第 2 个成立的城市，其 ID 号码为 000001000002. City 2 是属于州 2 的城市中第 1 个成立的城市，其ID 号码为 000002000001.· City 3 是属于州 1 的城市中第 1 个成立的城市，其 ID 号码为 000001000001

2 3
2 55
2 77
2 99

000002000001
000002000002
000002000003

提示

$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$ 是不同的

$输入的都是整数$