stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <iostream>

#include <map>

#include <string>



using namespace std;



int main() {

	int n, m;

	while (cin >> n, n) {

		char a, b;

		string str;

		map<char, char> to;

		for (int i = 0; i < n; ++i) {

			cin >> a >> b;

			to[a] = b;

		}

		cin >> m;

		for (int i = 0; i < m; ++i) {

			cin >> a;

			if (to[a]) a = to[a];

			str += a;

		}

		cout << str << endl;

	}

	return 0;

}

// Optimized solution to the same problem (faster):
#include <stdio.h>



int main() {

	char trans[256];

	char c, c2, str[10];

	long n, m, i;



	while (scanf("%ld", &n), n) {

		for (i = 0; i < 256; ++i)

			trans[i] = i;



		for (i = 0; i < n; ++i) {

			scanf("%s", str); c = str[0];

			scanf("%s", str); c2 = str[0];

			trans[c] = c2;

		}



		scanf("%ld", &m);



		for (i = 0; i < m; ++i) {

			scanf("%s", str); c = str[0];

			printf("%c", trans[c]);

		}

		puts("");

	}



	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstdio>

#include<iostream>

#include<algorithm>

#include<stack>

#include<cmath>

#include<vector>

using namespace std;

int n,m;

int p[100005]; 

int y[100005];

vector<int>v[100005];

int main(){

	scanf("%d%d",&n,&m);

	for(int i=1;i<=m;i++){

		scanf("%d%d",&p[i],&y[i]);

		v[p[i]].push_back(y[i]);

	} 

	for(int i=1;i<=n;i++) sort(v[i].begin(),v[i].end());

	for(int i=1;i<=m;i++){

		printf("%06d",p[i]);

		int k=lower_bound(v[p[i]].begin(),v[p[i]].end(),y[i])-v[p[i]].begin()+1;

		printf("%06d\n",k);

	}

	return 0;

}

// Optimized solution to the same problem (faster):
#include<iostream>

#include<algorithm>

#include<cstdio>

using namespace std;

struct node{

    int city;

    long long num;

    int no;

    int i;

}a[100000+5];

bool cmp(struct node A,struct node B){

    if(A.city < B.city){

        return true;

    }else if(A.city == B.city){

        if(A.num < B.num){

            return true;

        }else{

            return false;

        }

    }else {

        return false;

    }

};

bool cmp1(struct node A,struct node B){

    if(A.i < B.i){

        return true;

    }else {

        return false;

    }

}

int main(){

    int N,M;

    cin>>N>>M;

    for(int i = 0;i < M;i++){

        a[i].i = i;

        int city,num;

        cin>>city>>num;

        a[i].city = city;

        a[i].num = num;

    }

    sort(a,a+M,cmp);

    int flag = 1;

    for(int i = 0;i < M;i++){

        if(i == 0){

            a[i].no = flag;

        }else if(a[i].city != a[i-1].city){

            flag = 1;

        }

        a[i].no = flag;

        flag++;

    }

    sort(a,a+M,cmp1);

    for(int i = 0;i < M;i++){

        printf("%06d%06d\n",a[i].city,a[i].no);

    }

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

#define THE using

#define DARK namespace

#define ONE std

#define dbg(x) cout << #x << " = " << x << endl



THE DARK ONE;

int main(){

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

//    freopen("out.txt", "w", stdout);

//    freopen("input.txt", "r", stdin);

    vector<int> x(100005), y(100005), z[100005];

    int n, m;

    cin >> n >> m;

    for(int i = 0; i < m; i++){

        cin >> x[i] >> y[i];

        z[x[i]].push_back(y[i]);

    }

    for(int i = 1; i <= n; i++)

        sort(z[i].begin(), z[i].end());

    for(int i = 0; i < m; i++){

        long long s = (long long) x[i] * 1000000;

        s += lower_bound(z[x[i]].begin(), z[x[i]].end(), y[i]) - z[x[i]].begin() + 1;

        printf("%012lld\n", s);

    }

    return 0;

}


// Optimized solution to the same problem (faster):
#include<iostream>

#include<algorithm>

using namespace std;

struct P{

	int p,y,d;

	int b[15];

};

int cmp(P x1,P x2){

	if(x1.p==x2.p){

		return x1.y<x2.y;

	}

	return x1.p<x2.p;

}

int cmp1(P x1,P x2){

	return x1.d<x2.d;

}

P a[100010];

int main(){

	int n,m,i,j,k;

	cin >> n >> m;

	for(i=0;i<m;i++){

		cin >> a[i].p >> a[i].y;

		a[i].d=i;

		for(j=0;j<13;j++){

			a[i].b[j]=0;

		}

	}

	sort(a,a+m,cmp);

	int x=1,w;

	for(i=0;i<m;i++){

		if(i==0 || a[i].p!=a[i-1].p){

			x=1;

		}

		else{

			x++;

		}

		j=5;

		w=a[i].p;

		while(w){

			a[i].b[j]=w%10;

			w/=10;

			if(j==0)

				break;

			j--;

		}

		w=x;

		j=11;

		while(w){

			a[i].b[j]=w%10;

			w/=10;

			if(j==6)

				break;

			j--;

		}

	}

	sort(a,a+m,cmp1);

	for(i=0;i<m;i++){

		for(j=0;j<12;j++){

			cout << a[i].b[j];

		}

		cout << endl;

	}

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):


#include <iostream>

#include <cstdio>

#include <cmath>

#include <queue>

#include <map>

#include <cstring>

#include <string>

#include <set>

#include <vector>

#include <list>

#include <deque>

#include <algorithm>

#include <stack>

#include <numeric>

#include <time.h>

#include<iomanip>

#pragma warning(disable:4996)

using namespace std;

const int inf = 0x7f7f7f7f;

const long long mod = 1e9 + 7;

pair<int, int>q[120000];

set<int>p[120000];

map<int, int>a;

int main()

{

	int n, m;

	cin >> n >> m;

	set<int>::iterator iter;

	map<int, int>::iterator it;

	for (int i = 0; i < m; i++)

	{

		cin >> q[i].first >> q[i].second;

		p[q[i].first].insert(q[i].second);

	}

	for (int i = 1; i <=n; i++)

	{

		int k = 1;

		for (iter = p[i].begin(); iter != p[i].end(); iter++)

			a[*iter] = k++;

	}

	for (int i = 0; i < m; i++)

	{

		printf("%06d", q[i].first);

		it = a.find(q[i].second);

		printf("%06d\n", it->second);

	}

}

// 运行程序: Ctrl + F5 或调试 >“始执行(不调试)”菜单

// 调试程序: F5 或调试 >“开始调试”菜单

// 入门提示:

//   1. 使用解决方案资源管理器窗口添 加/管理文件

//   2. 使用团队资源管理器窗口连接到源代码管理

//   3. 使用输出窗口查看生成输出和其他消息

//   4. 使用错误列表窗口查看错误

//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目

//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件

// Optimized solution to the same problem (faster):
#include<iostream>

#include<algorithm>

using namespace std;

struct P{

	int p,y,d;

	int b[15];

};

int cmp(P x1,P x2){

	if(x1.p==x2.p){

		return x1.y<x2.y;

	}

	return x1.p<x2.p;

}

int cmp1(P x1,P x2){

	return x1.d<x2.d;

}

P a[100010];

int main(){

	int n,m,i,j,k;

	cin >> n >> m;

	for(i=0;i<m;i++){

		cin >> a[i].p >> a[i].y;

		a[i].d=i;

		for(j=0;j<13;j++){

			a[i].b[j]=0;

		}

	}

	sort(a,a+m,cmp);

	int x=1,w;

	for(i=0;i<m;i++){

		if(i==0 || a[i].p!=a[i-1].p){

			x=1;

		}

		else{

			x++;

		}

		j=5;

		w=a[i].p;

		while(w){

			a[i].b[j]=w%10;

			w/=10;

			if(j==0)

				break;

			j--;

		}

		w=x;

		j=11;

		while(w){

			a[i].b[j]=w%10;

			w/=10;

			if(j==6)

				break;

			j--;

		}

	}

	sort(a,a+m,cmp1);

	for(i=0;i<m;i++){

		for(j=0;j<12;j++){

			cout << a[i].b[j];

		}

		cout << endl;

	}

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for (int i = 0; i < n; i++)

const int MAX = 100005;

int P[MAX], Y[MAX];

vector<int> yd[MAX];

int main()

{

    int N, M;

    cin >> N >> M;

    rep(i, M)

    {

        cin >> P[i] >> Y[i];

        yd[P[i]].push_back(Y[i]);

    }

    rep(i, N)

    sort(yd[i + 1].begin(), yd[i + 1].end());

    rep(i, M)

    {

        printf("%06d", P[i]);

        printf("%06d\n", lower_bound(yd[P[i]].begin(), yd[P[i]].end(), Y[i]) - yd[P[i]].begin() + 1);

    }

    return 0;

}


// Optimized solution to the same problem (faster):
#include<iostream>

#include<algorithm>

using namespace std;

struct P{

	int p,y,d;

	int b[15];

};

int cmp(P x1,P x2){

	if(x1.p==x2.p){

		return x1.y<x2.y;

	}

	return x1.p<x2.p;

}

int cmp1(P x1,P x2){

	return x1.d<x2.d;

}

P a[100010];

int main(){

	int n,m,i,j,k;

	cin >> n >> m;

	for(i=0;i<m;i++){

		cin >> a[i].p >> a[i].y;

		a[i].d=i;

		for(j=0;j<13;j++){

			a[i].b[j]=0;

		}

	}

	sort(a,a+m,cmp);

	int x=1,w;

	for(i=0;i<m;i++){

		if(i==0 || a[i].p!=a[i-1].p){

			x=1;

		}

		else{

			x++;

		}

		j=5;

		w=a[i].p;

		while(w){

			a[i].b[j]=w%10;

			w/=10;

			if(j==0)

				break;

			j--;

		}

		w=x;

		j=11;

		while(w){

			a[i].b[j]=w%10;

			w/=10;

			if(j==6)

				break;

			j--;

		}

	}

	sort(a,a+m,cmp1);

	for(i=0;i<m;i++){

		for(j=0;j<12;j++){

			cout << a[i].b[j];

		}

		cout << endl;

	}

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

#define ff first

#define ss second

int main()

{

    int n,m;

    cin>>n>>m;

    vector<vector<int> > v(100000+3);



    vector<int>::iterator it;



    vector<pair<int,int> > vv;



    for(int i=1; i<=m; i++)

    {

        int a, b;

        cin>>a>>b;

        v[a].push_back(b);

        vv.push_back(make_pair(a,b));

    }



    for(int i=1; i<=n; i++)

    {

        sort(v[i].begin(),v[i].end());

    }

    int sz = vv.size();

    for(int i=0; i<sz; i++)

    {

        int x = vv[i].ff;

        int y = vv[i].ss;

        it = lower_bound(v[x].begin(),v[x].end(),y);



        int z = it-v[x].begin();

        printf("%06d%06d\n",x,z+1);

    }



    return 0;

}




// Optimized solution to the same problem (faster):
#include<iostream>

#include<algorithm>

using namespace std;

struct P{

	int p,y,d;

	int b[15];

};

int cmp(P x1,P x2){

	if(x1.p==x2.p){

		return x1.y<x2.y;

	}

	return x1.p<x2.p;

}

int cmp1(P x1,P x2){

	return x1.d<x2.d;

}

P a[100010];

int main(){

	int n,m,i,j,k;

	cin >> n >> m;

	for(i=0;i<m;i++){

		cin >> a[i].p >> a[i].y;

		a[i].d=i;

		for(j=0;j<13;j++){

			a[i].b[j]=0;

		}

	}

	sort(a,a+m,cmp);

	int x=1,w;

	for(i=0;i<m;i++){

		if(i==0 || a[i].p!=a[i-1].p){

			x=1;

		}

		else{

			x++;

		}

		j=5;

		w=a[i].p;

		while(w){

			a[i].b[j]=w%10;

			w/=10;

			if(j==0)

				break;

			j--;

		}

		w=x;

		j=11;

		while(w){

			a[i].b[j]=w%10;

			w/=10;

			if(j==6)

				break;

			j--;

		}

	}

	sort(a,a+m,cmp1);

	for(i=0;i<m;i++){

		for(j=0;j<12;j++){

			cout << a[i].b[j];

		}

		cout << endl;

	}

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

#define cc(a) cout << a << endl;

#define msg(a,b) cout << a << " : " << b << endl;

#define msg2(a,b,c) cout << a << " : " << b << " : " << c << endl;

#define msg3(a,b,c,d) cout << a << " : " << b << " : " << c << " : " << d << endl;



string makeString(long long int n){

    stringstream ss;

    string str;

    ss << n;

    ss >> str;

    if(str.size() == 1){

        return "00000" + str;

    }else if(str.size() == 2){

        return "0000" + str;

    }else if(str.size() == 3){

        return "000" + str;

    }else if(str.size() == 4){

        return "00" + str;

    }else if(str.size() ==5){

        return "0" + str;

    }else if(str.size() == 6){

        return str;

    }



}



int main(){

    long long int n,m,a,b;

    string ans;

    vector< pair<long long int , long long int> > vec2;

    vector<long long int> vec[100004];

    map<pair<long long int, long long int> , string> mp;

    cin >> n >> m;

    while(m--){

        cin >> a >> b;

        vec[a].push_back(b);

        vec2.push_back(make_pair(a,b));

    }

    for(int i=0;i<=n;i++){

        sort(vec[i].begin(),vec[i].end());

    }

    for(int i=1;i<=n;i++){

        for(int j =0;j<vec[i].size();j++){

            ans = makeString(i) + makeString(j+1);

            mp[ make_pair(i, vec[i][j]) ] = ans;

        }

    }

    for(int i=0;i<vec2.size();i++){

        cout << mp[ make_pair( vec2[i].first, vec2[i].second ) ] << endl;

    }



    return 0;

}


// Optimized solution to the same problem (faster):
#include<iostream>

#include<algorithm>

using namespace std;

struct P{

	int p,y,d;

	int b[15];

};

int cmp(P x1,P x2){

	if(x1.p==x2.p){

		return x1.y<x2.y;

	}

	return x1.p<x2.p;

}

int cmp1(P x1,P x2){

	return x1.d<x2.d;

}

P a[100010];

int main(){

	int n,m,i,j,k;

	cin >> n >> m;

	for(i=0;i<m;i++){

		cin >> a[i].p >> a[i].y;

		a[i].d=i;

		for(j=0;j<13;j++){

			a[i].b[j]=0;

		}

	}

	sort(a,a+m,cmp);

	int x=1,w;

	for(i=0;i<m;i++){

		if(i==0 || a[i].p!=a[i-1].p){

			x=1;

		}

		else{

			x++;

		}

		j=5;

		w=a[i].p;

		while(w){

			a[i].b[j]=w%10;

			w/=10;

			if(j==0)

				break;

			j--;

		}

		w=x;

		j=11;

		while(w){

			a[i].b[j]=w%10;

			w/=10;

			if(j==6)

				break;

			j--;

		}

	}

	sort(a,a+m,cmp1);

	for(i=0;i<m;i++){

		for(j=0;j<12;j++){

			cout << a[i].b[j];

		}

		cout << endl;

	}

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int>P;

int n,m;

vector<P> v,v1;

int s[100001];

string f(int x){

    if(x<10)return "00000";

    else if(x<100)return "0000";

    else if(x<1000)return "000";

    else if(x<10000)return "00";

    else if(x<100000)return "0";

    else return "";

}

int main(void){

    cin>>n>>m;

    for(int i=0;i<m;i++){

        int a,b;

        cin>>a>>b;

        v.push_back(P(a,b));

        v1.push_back(P(a,b));

        s[a]++;

    }

    for(int i=0;i<100000;i++){

        s[i+1]+=s[i];

        //cout<<s[i]<<endl;

    }

    

    sort(v.begin(),v.end());

    for(int i=0;i<m;i++){

        cout<<f(v1[i].first)<<v1[i].first;

        int mid=upper_bound(v.begin(),v.end(),v1[i])-v.begin();

        mid-=s[v1[i].first-1];

        cout<<f(mid)<<mid<<endl;

    }

}


// Optimized solution to the same problem (faster):
#include <iostream>

#include<bits/stdc++.h>

#define F first

#define S second

using namespace std;

typedef long long ll;

typedef pair<pair<ll,ll>,ll>P;

ll n,m,a,b;

vector<P>v;

ll ans[100000][2];

int main(void){

    cin>>n>>m;

    for(int i=0;i<m;i++){

        cin>>a>>b;

        v.push_back({{a,b},i});

    }

    sort(v.begin(),v.end());

    //cout<<setfill('0')<<setw(4)<<12<<endl;

    ll l=0,ch=0;

    for(int i=0;i<m;i++){

        if(v[i].F.F!=ch){

            ch=v[i].F.F;

            l=i;

        }

        ans[v[i].S][0]=v[i].F.F;

        ans[v[i].S][1]=i-l+1;

    }

    for(int i=0;i<m;i++){

        cout<<setfill('0')<<setw(6)<<ans[i][0];

        cout<<setfill('0')<<setw(6)<<ans[i][1]<<endl;

    }

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



typedef long long ll;



int N, M;

int P[100000], Y[100000];

vector<int> yd[100001];



int main() {

    scanf("%d %d ", &N, &M);

    for (int i = 0; i < M; i++) {

        scanf("%d %d ", &P[i], &Y[i]), yd[P[i]].push_back(Y[i]);

    }



    for (int i = 0; i < N; i++) sort(yd[i + 1].begin(), yd[i + 1].end());



    for (int i = 0; i < M; i++) {

        auto lb  = lower_bound(yd[P[i]].begin(), yd[P[i]].end(), Y[i]);

        int rank = lb - yd[P[i]].begin() + 1;

        printf("%06d%06d\n", P[i], rank);

    }

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

//template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

//template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }



/* attention

    long longのシフト演算には気をつけよう

    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも

*/



int main(){

    int N, M; cin >> N >> M;

    vector<int> p(M), y(M);

    vector<int> order[N+1];



    for(int i=0; i<M; i++){

        cin >> p[i] >> y[i];

        order[p[i]].push_back(y[i]);

    }



    for(int i=1; i<=N; i++) sort(order[i].begin(), order[i].end());



    for(int i=0; i<M; i++){

        auto itr = lower_bound(order[p[i]].begin(), order[p[i]].end(), y[i]);

        int rank = itr - order[p[i]].begin() + 1;

        printf("%06d%06d\n", p[i], rank);

    }

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;





int main(){

    int P[100000], Y[100000];

    vector<int> V[100001];

    int N,M;

    scanf("%d %d", &N, &M);



    for(int i=0; i<M; i++){

        scanf("%d %d", &P[i], &Y[i]);

        V[P[i]].push_back(Y[i]);

    }



    for(int i=1; i<N+1; i++){

        sort(V[i].begin(), V[i].end());

    }



    for(int i=0; i<M; i++){

        auto it=lower_bound(V[P[i]].begin(), V[P[i]].end(), Y[i]);

        int rank=it-V[P[i]].begin()+1;

        printf("%06d%06d\n", P[i], rank);

    }



    return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

//template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

//template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }



/* attention

    long longのシフト演算には気をつけよう

    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも

*/



int main(){

    int N, M; cin >> N >> M;

    vector<int> p(M), y(M);

    vector<int> order[N+1];



    for(int i=0; i<M; i++){

        cin >> p[i] >> y[i];

        order[p[i]].push_back(y[i]);

    }



    for(int i=1; i<=N; i++) sort(order[i].begin(), order[i].end());



    for(int i=0; i<M; i++){

        auto itr = lower_bound(order[p[i]].begin(), order[p[i]].end(), y[i]);

        int rank = itr - order[p[i]].begin() + 1;

        printf("%06d%06d\n", p[i], rank);

    }

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;



int main(void){

    int N,M; cin >> N >> M;

    vector<int> P(M), Y(M);

    vector<int> V[100001];



    for(int i=0; i<M; i++){

        cin >> P[i] >> Y[i];

        V[P[i]].push_back(Y[i]);

    }



    for(int i=1; i<=N; i++) sort(V[i].begin(), V[i].end());



    for(int i=0; i<M; i++){

        auto it1=lower_bound(V[P[i]].begin(), V[P[i]].end(), Y[i]);

        int rank=it1-V[P[i]].begin()+1;

        printf("%06d%06d\n", P[i], rank);

    }



}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

//template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

//template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }



/* attention

    long longのシフト演算には気をつけよう

    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも

*/



int main(){

    int N, M; cin >> N >> M;

    vector<int> p(M), y(M);

    vector<int> order[N+1];



    for(int i=0; i<M; i++){

        cin >> p[i] >> y[i];

        order[p[i]].push_back(y[i]);

    }



    for(int i=1; i<=N; i++) sort(order[i].begin(), order[i].end());



    for(int i=0; i<M; i++){

        auto itr = lower_bound(order[p[i]].begin(), order[p[i]].end(), y[i]);

        int rank = itr - order[p[i]].begin() + 1;

        printf("%06d%06d\n", p[i], rank);

    }

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



int main() {

  int N,M;

  scanf("%d %d", &N,&M);

  int P[M],Y[M];

  for (int i = 0; i < M; ++i) {

    scanf("%d %d", &P[i],&Y[i]);

  }



  vector<int> yd[100001];

  for (int i = 0; i < M; ++i){

    yd[P[i]].push_back(Y[i]);

  }

  for (int i = 0; i < N; ++i){

    sort(yd[i+1].begin(),yd[i+1].end());

  }



  for (int i = 0;i < M;++i) printf("%06d%06d\n", P[i],int(lower_bound(yd[P[i]].begin() ,yd[P[i]].end(), Y[i]) - yd[P[i]].begin())+1);

  



}




// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



int main() {

  int N,M;

  scanf("%d %d", &N,&M);

  int P[M],Y[M];

  vector<pair<pair<int,int>,int>> cities;

  for (int i = 0; i < M; ++i) {

    scanf("%d %d", &P[i],&Y[i]);

    cities.push_back(make_pair(make_pair(Y[i], P[i]), i));

  }



  sort(cities.begin(), cities.end());



  vector<int>num(M), cnt(N+1);



  for (int i = 0; i < cities.size(); ++i){

    ++cnt[cities[i].first.second];

    num[cities[i].second] = cnt[cities[i].first.second];

  }



  for (int i = 0;i < M;++i) printf("%06d%06d\n", P[i],num[i]);

  





  



}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <vector>

#include <algorithm>

#include <cstdio>

using namespace std;



int main()

{

  int n, m;

  cin >> n >> m;



  vector<pair<int, int> > v;

  vector<int> u[100001];

  for(int i = 0; i < m; i++){

    int p, y;

    cin >> p >> y;

    v.push_back(make_pair(p, y));

    u[p].push_back(y);

  }



  for(int i = 1; i <= n; i++){

    sort(u[i].begin(), u[i].end());

  }



  for(int i = 0; i < m; i++){

    int p = v[i].first;

    printf("%06d%06d\n", p, (int)(lower_bound(u[p].begin(), u[p].end(), v[i].second) - u[p].begin() + 1));

  }



  return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



#ifdef LOCAL

    #define eprintf(...) fprintf(stderr, __VA_ARGS__)

#else

        #define eprintf(...) 42

#endif



#define rep(i,n) for(int i=0;i<(int)(n);i++)

#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)

#define all(x) (x).begin(),(x).end()

#define foreach(u,v) for(auto (u) : (v))

#define pb push_back

#define mp make_pair

#define mt make_tuple



typedef long long ll;

typedef pair<int, int> pii;

typedef vector<int> vi;

typedef vector<vi> vvi;

typedef pair<ll, ll> pll;

typedef vector<ll> vl;



const int inf = 1e9;

const ll linf = 1LL<<60;

const ll mod = 1e9 + 7;

const double eps = 1e-9;



/*

*/



int main()

{

  int n, m;

  cin >> n >> m;



  vector<pii> v[n+1];

  rep(i, m){

    int p, y;

    cin >> p >> y;

    v[p].pb({y, i}); 

  }



  rep(i, n+1) sort(all(v[i]));



  vector<ll> ans(m);

  rep(i, n+1){

    rep(j, v[i].size()){

      ans[v[i][j].second] = (ll)i*1000000+j+1;

    }

  }



  for(ll i : ans){

    printf("%012lld\n", i);

  }



  return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> P;

int main(void){

  int n,m,i,j,pi,y;

  P ans[100010];

  vector<P> p[100010];

  cin >> n >> m;

  for (i=0;i<m;i++){

    cin >> pi >> y;

    p[pi-1].push_back(P(y,i));

  }

  for (i=0;i<n;i++) sort(p[i].begin(),p[i].end());

  for (i=0;i<n;i++){

    for (j=0;j<p[i].size();j++) ans[p[i][j].second]=P(i+1,j+1);

  }

  for (i=0;i<m;i++){

    int d=10,k=5;

    while (ans[i].first >= d){

      d*=10;

      k--;

    }

    for (j=0;j<k;j++) cout << 0;

    cout << ans[i].first;

    d=10;

    k=5;

    while (ans[i].second >= d){

      d*=10;

      k--;

    }

    for (j=0;j<k;j++) cout << 0;

    cout << ans[i].second << endl;

  }

  return 0;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

typedef long long ll;

typedef pair<int, int> P;





int dn(int x) {

	if (x >= 100000) return 0;

	else if (x >= 10000) return 1;

	else if (x >= 1000) return 2;

	else if (x >= 100) return 3;

	else if (x >= 10) return 4;

	else return 5;

}



int main(void) {

	int n, m, i, j, p[100003], y, b[100003], k;

	vector<P> v[100003];



	cin >> n >> m;

	for (i = 0; i < m; i++) {

		cin >> p[i] >> y;

		v[p[i]].push_back(P(y, i));

	}



	for (i = 1; i <= n; i++) {

		sort(v[i].begin(), v[i].end());

		for (j = 0; j < v[i].size(); j++) {

			b[v[i][j].second] = j + 1;

		}

	}



	for (i = 0; i < m; i++) {

		k = dn(p[i]);

		for (j = 0; j < k; j++) cout << 0;

		cout << p[i];

		k = dn(b[i]);

		for (j = 0; j < k; j++) cout << 0;

		cout << b[i] << endl;

	}



	return 0;

}

// Fastest known solution for this problem: