#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <limits>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <functional>
#include <iomanip>

using namespace std;

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...) 42
#endif
using ll = long long;
using vll = std::vector<ll>;
using vvll = std::vector<vll>;
using vvvll = std::vector<vvll>;
#define reps(i, S, E) for (ll i = (S); i <= (E); i++)
#define rep(i, N) reps(i, 0, N-1)
#define deps(i, E, S) for (ll i = (E); i >= (S); i--)
#define dep(i, N) deps(i, N-1, 0)
const ll INF = 1LL << 60;
const int INF_INT = 1 << 30;

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; }
struct mll {
	static ll MOD;
	ll val;
	mll(ll v = 0) : val(v % MOD) { if (val < 0) val += MOD; }
	mll operator - () const { return -val; }
	mll operator + (const mll &b) const { return val + b.val; }
	mll operator - (const mll &b) const { return val - b.val; }
	mll operator * (const mll &b) const { return val * b.val; }
	mll operator / (const mll &b) const { return mll(*this) /= b; }
	mll operator + (ll b) const { return *this + mll(b); }
	mll operator - (ll b) const { return *this - mll(b); }
	mll operator * (ll b) const { return *this * mll(b); }
	friend mll operator + (ll a, const mll &b) { return b + a; }
	friend mll operator - (ll a, const mll &b) { return -b + a; }
	friend mll operator * (ll a, const mll &b) { return b * a; }
	mll &operator += (const mll &b) { val = (val + b.val) % MOD; return *this; }
	mll &operator -= (const mll &b) { val = (val + MOD - b.val) % MOD; return *this; }
	mll &operator *= (const mll &b) { val = (val*b.val) % MOD; return *this; }
	mll &operator /= (const mll &b) {
		ll c = b.val, d = MOD, u = 1, v = 0;
		while (d) {
			ll t = c / d;
			c -= t * d; swap(c, d);
			u -= t * v; swap(u, v);
		}
		val = val * u % MOD;
		if (val < 0) val += MOD;
		return *this;
	}
	mll &operator += (ll b) { return *this += mll(b); }
	mll &operator -= (ll b) { return *this -= mll(b); }
	mll &operator *= (ll b) { return *this *= mll(b); }
	mll &operator /= (ll b) { return *this /= mll(b); }
	bool operator == (const mll &b) { return val == b.val; }
	bool operator != (const mll &b) { return val != b.val; }
	bool operator == (ll b) { return *this == mll(b); }
	bool operator != (ll b) { return *this != mll(b); }
	friend bool operator == (ll a, const mll &b) { return mll(a) == b.val; }
	friend bool operator != (ll a, const mll &b) { return mll(a) != b.val; }
	friend ostream &operator << (ostream &os, const mll &a) { return os << a.val; }
	friend istream &operator >> (istream &is, mll &a) { return is >> a.val; }
	static mll Combination(ll a, ll b) {
		chmin(b, a - b);
		if (b < 0) return mll(0);
		mll c = 1;
		rep(i, b) c *= a - i;
		rep(i, b) c /= i + 1;
		return c;
	}
};
using vmll = std::vector<mll>;
using vvmll = std::vector<vmll>;
using vvvmll = std::vector<vvmll>;
using vvvvmll = std::vector<vvvmll>;

//struct Fast {
//	Fast() {
//		cin.tie(0);
//		ios::sync_with_stdio(false);
//		cout << fixed << setprecision(std::numeric_limits<double>::max_digits10);
//	}
//} fast; //cin,cout�������̂��܂��Ȃ��{�����w��
//
//ll mll::MOD = (ll)(1e9 + 7);// 998244353ll;


/*
int main() {
	string s;
	cin >> s;
	ll len_s = s.size();

	switch (s[0])
	{
	case 'A':
		cout << "T" << endl;
		break;
	case 'C':
		cout << "G" << endl;
		break;
	case 'G':
		cout << "C" << endl;
		break;
	case 'T':
		cout << "A" << endl;
		break;
	default:
		break;
	}

	return 0;
}
*/

//AtCoder Beginner Contest 122 - 113 - C
struct LLPair {
	ll i = 0;
	ll p = 0;
	ll y = 0;
	ll id = 0;
	LLPair() {}
	LLPair(ll i, ll p, ll y) {
		this->i = i;
		this->p = p;
		this->y = y;
	}
};

int main() {
	ll N;
	cin >> N;
	ll M;
	cin >> M;
	vector<LLPair> P(M);
	rep(i, M) {
		cin >> P[i].p >> P[i].y;
		P[i].i = i;
	}

	std::sort(P.begin(), P.end(), [](const LLPair &a, const LLPair &b) {
		return a.y < b.y; //�~���ɂ���ɂ� > �Ƃ���
	});

	vll pCount(N + 1, 0);

	rep(i, M) {
		pCount[P[i].p]++;
		P[i].id = P[i].p * 1000000 + pCount[P[i].p];
	}

	std::sort(P.begin(), P.end(), [](const LLPair &a, const LLPair &b) {
		return a.i < b.i; //�~���ɂ���ɂ� > �Ƃ���
	});

	rep(i, M) {
		std::cout << std::setfill('0') << std::right << std::setw(12) << P[i].id << endl;
	}

	return 0;
}


/*
int main() {
	ll N;
	cin >> N;
	ll K;
	cin >> K;
	vector<ll> h(N);
	rep(i, N) {
		cin >> h[i];
	}

	std::sort(h.begin(), h.end(), std::greater<ll>());

	ll result = INF;

	reps(i, 0, N - K) {
		chmin(result, h[i] - h[i + K - 1]);
	}

	cout << result << endl;

	return 0;
}
*/

/*
int main() {
	ll N;
	cin >> N;
	vector<ll> h(N);
	rep(i, N) {
		cin >> h[i];
	}

	ll result = 0;

	rep(i, 101) {
		bool start = false;

		rep(j, N) {
			if (start == false) {
				if (h[j] > 0) {
					start = true;
					h[j]--;
					result++;
				}
			}
			else {
				if (h[j] == 0) {
					start = false;
				}
				else {
					h[j]--;
				}
			}
		}
	}

	cout << result << endl;

	return 0;
}
*/

/*
int main() {
	int N;
	cin >> N;
	vector<int> A(N);
	rep(i, N) {
		cin >> A[i];
	}

	int result = INF_INT;
	int dev = 0;

	while (true) {
		vector<int> B(A.size());
		rep(i, A.size()) {
			B[i] = A[i];
		}
		std::sort(B.begin(), B.end());
		A.clear();

		if (dev == B[0]) {
			result = dev;
			break;
		}
		else if (dev == 1) {
			result = 1;
			break;
		}
		else {
			dev = B[0];
		}

		A.push_back(dev);
		reps(i, 1, B.size() - 1) {
			int temp = B[i] % dev;
			if (temp > 0) {
				A.push_back(temp);
			}
		}
	}

	cout << result << endl;

	return 0;
}
*/

/*
int main() {
	ll N;
	cin >> N;
	ll Q;
	cin >> Q;
	string S;
	cin >> S;
	ll len_S = S.size();
	vll l(Q);
	vll r(Q);
	rep(i, Q) {
		cin >> l[i] >> r[i];
	}

	vll totalAofAC(len_S + 10, 0);
	reps(i, 1, len_S - 1) {
		totalAofAC[i] = totalAofAC[i - 1];
		if (S[i - 1] == 'A' && S[i] == 'C') {
			totalAofAC[i]++;
		}
	}

	rep(q, Q) {
		ll result = totalAofAC[r[q] - 1] - totalAofAC[l[q] - 1];

		cout << result << endl;
	}

	return 0;
}
*/

//AtCoder Beginner Contest 121 - C
/*
struct LLPair {
	ll a = 0;
	ll b = 0;
	LLPair() {}
	LLPair(ll a, ll b) {
		this->a = a;
		this->b = b;
	}
};

int main() {
	ll N;
	cin >> N;
	ll M;
	cin >> M;
	vector<LLPair> p(N);
	rep(i, N) {
		cin >> p[i].a >> p[i].b;
	}

	std::sort(p.begin(), p.end(), [](const LLPair &a, const LLPair &b) {
		return a.a < b.a; //�~���ɂ���ɂ� > �Ƃ���
	});

	ll result = 0;

	rep(i, N) {
		if (p[i].b >= M) {
			result += p[i].a * M;
			break;
		}
		else {
			result += p[i].a * p[i].b;
			M -= p[i].b;
		}
	}

	cout << result << endl;

	return 0;
}
*/

//AtCoder Beginner Contest 124 - 125 - A / B
/*
int main() {
	ll N;
	scanf("%lld", &N);
	vector<ll> H(N);
	for (ll i = 0; i < N; i++) {
		scanf("%lld", &H[i]);
	}

	ll result = 1;
	ll maxH = H[0];

	reps(i, 1, N - 1) {
		if (maxH <= H[i]) {
			result++;
		}

		maxH = max(maxH, H[i]);
	}

	printf("%lld\n", result);
}
*/

/*
int main() {
	ll A;
	scanf("%lld", &A);
	ll B;
	scanf("%lld", &B);

	ll result = 0;

	if (A > B) {
		result += A;
		A--;
	}
	else {
		result += B;
		B--;
	}


	if (A > B) {
		result += A;
		A--;
	}
	else {
		result += B;
		B--;
	}

	printf("%lld\n", result);
}
*/

/*
int main() {
	ll N;
	scanf("%lld", &N);
	vector<ll> V(N);
	for (ll i = 0; i < N; i++) {
		scanf("%lld", &V[i]);
	}
	vector<ll> C(N);
	for (ll i = 0; i < N; i++) {
		scanf("%lld", &C[i]);
	}

	ll result = 0;

	rep(i, N) {
		if (V[i] - C[i] > 0) {
			result += V[i] - C[i];
		}
	}

	printf("%lld\n", result);
}
*/

/*
int main() {
	ll A;
	scanf("%lld", &A);
	ll B;
	scanf("%lld", &B);
	ll T;
	scanf("%lld", &T);

	ll result = (ll)(T / A) * B;

	printf("%lld\n", result);
}
*/

//AtCoder Beginner Contest 131 - 127 - A
/*
int main() {
	ll A;
	scanf("%lld", &A);
	ll B;
	scanf("%lld", &B);

	ll result = 0;

	if (A >= 13) {
		result = B;
	}
	else if (A >= 6) {
		result = B / 2;
	}

	printf("%lld\n", result);
}
*/

/*
int main() {
	ll A;
	scanf("%lld", &A);
	ll P;
	scanf("%lld", &P);

	ll bit = A * 3 + P;

	ll result = bit / 2;

	printf("%lld\n", result);
}
*/

/*
int main() {
	vector<ll> A(3);
	for (ll i = 0; i < 3; i++) {
		scanf("%lld", &A[i]);
	}

	ll result = INF;

	rep(i, 3) {
		reps(j, i + 1, 2) {
			result = min(result, A[i] + A[j]);
		}
	}

	printf("%lld\n", result);
}
*/

/*
int main() {
	ll X;
	scanf("%lld", &X);
	ll A;
	scanf("%lld", &A);

	if (X < A) {
		printf("0\n");
	}
	else {
		printf("10\n");
	}
}
*/

/*
int main() {
	char S[101010];
	scanf("%s", S);
	ll len = strlen(S);
	
	rep(i, len - 1) {
		if (S[i] == S[i + 1]) {
			printf("Bad\n");
			return 0;
		}
	}
	printf("Good\n");

}
*/

//AtCoder Beginner Contest 131 - 127 - B
/*
int main() {
	ll r;
	scanf("%lld", &r);
	ll d;
	scanf("%lld", &d);
	ll x;
	scanf("%lld", &x);

	ll result = x;
	rep(i, 10) {
		result = max(0ll, result * r - d);
		printf("%lld\n", result);
	}
}
*/

/*
struct LLPair {
	string s;
	ll a = 0;
	ll b = 0;
	LLPair() {}
	LLPair(string s, ll a, ll b) {
		this->s = s;
		this->a = a;
		this->b = b;
	}
};

int main() {
	ll N;
	cin >> N;
	vector<LLPair> P(N);
	rep(i, N) {
		cin >> P[i].s >> P[i].b;
		P[i].a = i + 1;
	}

	std::sort(P.begin(), P.end(), [](const LLPair &a, const LLPair &b) {
		if (a.s == b.s) {
			return a.b > b.b; //�~���ɂ���ɂ� > �Ƃ���
		}
		else {
			return a.s < b.s;
		}
	});

	rep(i, N) {
		printf("%lld\n", P[i].a);
	}
}
*/

/*
int main() {
	ll N;
	scanf("%lld", &N);
	vector<ll> W(N);
	for (ll i = 0; i < N; i++) {
		scanf("%lld", &W[i]);
	}

	ll result = INF;

	rep(i, N - 1) {
		ll S1 = 0;
		ll S2 = 0;
		rep(j, N) {
			if (j <= i) {
				S1 += W[j];
			}
			else {
				S2 += W[j];
			}
		}
		result = min(result, abs(S1 - S2));
	}

	printf("%lld\n", result);
}
*/

/*
int main() {
	ll N;
	scanf("%lld", &N);
	ll X;
	scanf("%lld", &X);
	vector<ll> L(N);
	for (ll i = 0; i < N; i++) {
		scanf("%lld", &L[i]);
	}

	ll bound = 0;
	ll result = 1;

	rep(i, N) {
		bound += L[i];
		if (bound <= X) {
			result++;
		}
	}

	printf("%lld\n", result);
}
*/

/*
int main() {
	ll N;
	scanf("%lld", &N);
	ll L;
	scanf("%lld", &L);

	ll result = 0;

	if (L > 0) {
		//��ԍŏ��̂�񂲂𖳎�
		reps(i, L + 1, L + N - 1) {
			result += i;
		}
	}
	else if (L + N <= 0) {
		//��ԍŌ�̂�񂲂𖳎�
		reps(i, L, L + N - 2) {
			result += i;
		}
	}
	else {
		//�[���̂�񂲂𖳎�
		reps(i, L, L + N - 1) {
			result += i;
		}
	}

	printf("%lld\n", result);
}
*/

//AtCoder Beginner Contest 123 - CBA
/*
int main() {
	vector<ll> A(5);
	for (ll i = 0; i < 5; i++) {
		scanf("%lld", &A[i]);
	}
	ll k;
	scanf("%lld", &k);
	
	rep(i, 5) {
		reps(j, i + 1, 5 - 1) {
			if (A[j] - A[i] > k) {
				printf(":(\n");
				return 0;
			}
		}
	}

	printf("Yay!\n");
}
*/

/*
int main() {
	vector<ll> A(5);
	for (ll i = 0; i < 5; i++) {
		scanf("%lld", &A[i]);
	}

	ll lastIndex = 0;
	ll minMod = INF;
	rep(i, 5) {
		if (A[i] % 10 < minMod && A[i] % 10 > 0) {
			minMod = A[i] % 10;
			lastIndex = i;
		}
	}

	ll result = A[lastIndex];
	rep(i, 5) {
		if (i == lastIndex) {
			continue;
		}

		result += (ll)ceil((double)A[i] / 10.0) * 10;
	}

	printf("%lld\n", result);
}
*/

/*
int main() {
	ll N;
	scanf("%lld", &N);
	vector<ll> A(5);
	for (ll i = 0; i < 5; i++) {
		scanf("%lld", &A[i]);
	}

	ll bottleNeck = INF;
	rep(i, 5) {
		bottleNeck = min(bottleNeck, A[i]);
	}

	ll result = 5 + (ll)ceil((double)N / (double)bottleNeck) - 1;

	printf("%lld\n", result);
}
*/

//AtCoder Beginner Contest 132 - A B
/*
int main() {
	ll N;
	scanf("%lld", &N);
	vector<ll> p(N);
	for (ll i = 0; i < N; i++) {
		scanf("%lld", &p[i]);
	}

	ll result = 0;

	reps(i, 0, N - 3) {
		if (p[i] < p[i + 1] && p[i + 1] < p[i + 2]) {
			result++;
		}
		else if (p[i] > p[i + 1] && p[i + 1] > p[i + 2]) {
			result++;
		}
	}

	printf("%lld\n", result);
}
*/

/*
int main() {
	char S[101010];
	scanf("%s", S);
	ll len = strlen(S);

	vll count(26);
	rep(i, len) {
		count[S[i] - 'A']++;
	}


	rep(i, 26) {
		if (count[i] != 0 && count[i] != 2) {
			printf("No\n");
			return 0;
		}
	}

	printf("Yes\n");
}
*/

//AtCoder Beginner Contest 133 - A B
/*
int main() {
	ll N;
	scanf("%lld", &N);
	ll D;
	scanf("%lld", &D);
	vvll X(N, vll(D, 0));
	rep(i, N) rep(j, D) {
		ll x;
		scanf("%lld", &x);
		X[i][j] = x;
	}

	ll result = 0;

	reps(i, 0, N - 1) {
		reps(j, i + 1, N - 1) {
			ll d2 = 0;
			rep(k, D) {
				ll sub = X[i][k] - X[j][k];
				d2 += sub * sub;
			}

			rep(k, 16000) {
				if (k * k == d2) {
					result++;
					break;
				}
			}
		}
	}

	printf("%lld\n", result);
}
*/

/*
int main() {
	ll N;
	scanf("%lld", &N);
	ll A;
	scanf("%lld", &A);
	ll B;
	scanf("%lld", &B);

	ll result = min(A * N, B);

	printf("%lld\n", result);
}
*/

//AtCoder Beginner Contest 134 - A B
/*
int main() {
	ll N;
	scanf("%lld", &N);
	ll D;
	scanf("%lld", &D);

	ll result = (ll)ceil((double)N / (1 + D * 2));

	printf("%lld\n", result);
}
*/

/*
int main() {
	ll r;
	scanf("%lld", &r);

	ll result = 3 * r * r;

	printf("%lld\n", result);
}
*/

//AtCoder Beginner Contest 135 - B
/*
int main() {
	ll N;
	scanf("%lld", &N);
	vector<ll> p(N);
	for (ll i = 0; i < N; i++) {
		scanf("%lld", &p[i]);
	}

	ll err = 0;
	rep(i, N) {
		if (p[i] != i + 1) {
			err++;
		}
	}

	if (err <= 2) {
		printf("YES\n");
	}
	else {
		printf("NO\n");
	}
}
*/

//AtCoder Beginner Contest 135 - A
/*
int main() {
	ll A;
	scanf("%lld", &A);
	ll B;
	scanf("%lld", &B);

	if (abs(A - B) % 2 == 1) {
		printf("IMPOSSIBLE\n");
		return 0;
	}

	ll ans = abs(A - B) / 2;
	ll result = min(A, B) + ans;

	printf("%lld\n", result);
}
*/

//AtCoder Beginner Contest 126 - B
/*
int main() {
	char s[101010];
	scanf("%s", s);
	ll len = strlen(s);

	ll front = (s[0] - '0') * 10 + (s[1] - '0');
	ll back = (s[2] - '0') * 10 + (s[3] - '0');

	if ((front > 12 && back > 12) || (front > 12 && back == 0) || (back > 12 && front == 0) || (back == 0 && front == 0)) {
		printf("NA\n");
	}
	else if (front > 12 || front == 0) {
		printf("YYMM\n");
	}
	else if (back > 12 || back == 0) {
		printf("MMYY\n");
	}
	else {
		printf("AMBIGUOUS\n");
	}
}
*/

//AtCoder Beginner Contest 126 - A
/*
int main() {
	ll N;
	scanf("%lld", &N);
	ll K;
	scanf("%lld", &K);
	char s[101010];
	scanf("%s", s);
	ll len = strlen(s);

	s[K - 1] = s[K - 1] - 'A' + 'a';

	printf("%s\n", s);
}
*/

Measured memory_bytes: 5376