AtCoder Beginner Contest 113 - ID

In Republic of Atcoder, there are N prefectures, and a total of M cities that belong to those prefectures.
City i is established in year Y_i and belongs to Prefecture P_i.
You can assume that there are no multiple cities that are established in the same year.
It is decided to allocate a 12-digit ID number to each city.
If City i is the x-th established city among the cities that belong to Prefecture i, the first six digits of the ID number of City i is P_i, and the last six digits of the ID number is x.
Here, if P_i or x (or both) has less than six digits, zeros are added to the left until it has six digits.
Find the ID numbers for all the cities.
Note that there can be a prefecture with no cities.

-----Constraints-----
 - 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 are all different.
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N M
P_1 Y_1
:
P_M Y_M

-----Output-----
Print the ID numbers for all the cities, in ascending order of indices (City 1, City 2, ...).

-----Sample Input-----
2 3
1 32
2 63
1 12

-----Sample Output-----
000001000002
000002000001
000001000001

 - As City 1 is the second established city among the cities that belong to Prefecture 1, its ID number is 000001000002.
 - As City 2 is the first established city among the cities that belong to Prefecture 2, its ID number is 000002000001.
 - As City 3 is the first established city among the cities that belong to Prefecture 1, its ID number is 000001000001.

Difficulty: EASY

Starter code:

Solutions:
(n, m) = list(map(int, input().split()))
pref = [[] for _ in range(n + 1)]
py = [[i] + list(map(int, input().split())) for i in range(m)]
py.sort(key=lambda x: (x[1], x[2]))
ans = list()
now = 0
cnt = 0
for x in py:
	cnt = 1 if now != x[1] else cnt + 1
	now = x[1]
	ans.append([x[0], x[1], cnt])
ans.sort(key=lambda x: x[0])
for x in ans:
	print(str(x[1]).zfill(6) + str(x[2]).zfill(6))


import sys
from operator import itemgetter
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

def main():
	(N, M, *PY) = map(int, read().split())
	city = [(p, y, i) for (i, (p, y)) in enumerate(zip(*[iter(PY)] * 2))]
	city.sort(key=itemgetter(1))
	counter = [0] * (N + 1)
	ans = [0] * M
	for (p, y, i) in city:
		counter[p] += 1
		ans[i] = f'{p:>06}{counter[p]:>06}'
	print(*ans, sep='\n')
	return

def __starting_point():
	main()
__starting_point()


from collections import defaultdict
import bisect
(n, m) = map(int, input().split())
py = [[int(i) for i in input().split()] for _ in range(m)]
dic = defaultdict(list)
for (p, y) in sorted(py):
	dic[p] += [y]
for (p, y) in py:
	idx = bisect.bisect_right(dic[p], y)
	print('{:06g}{:06g}'.format(p, idx))


import bisect
(n, m) = map(int, input().split(' '))
py = [list(map(int, input().split(' '))) for i in range(m)]
n_py = sorted(py)
a = [[] for i in range(n + 1)]
for (i, j) in py:
	a[i].append(j)
for i in range(1, n + 1):
	a[i] = sorted(a[i])
for (i, j) in py:
	(ix, ij) = map(str, [i, bisect.bisect(a[i], j)])
	print('0' * (6 - len(ix)) + ix + '0' * (6 - len(ij)) + ij)


import sys
import bisect
(n, m) = map(int, input().split())
l = [[int(i) for i in l.split()] for l in sys.stdin]
s = [[0] for i in range(10 ** 5 + 1)]
for i in l:
	s[i[0]].append(i[1])
for i in range(len(s)):
	s[i].sort()
for i in l:
	print('{:06}{:06}'.format(i[0], bisect.bisect_left(s[i[0]], i[1])))


(n, m) = map(int, input().split())
t = [[] for _ in range(n)]
for i in range(m):
	(p, y) = map(int, input().split())
	t[p - 1].append((y, i))
ans = [''] * m
for (i, j) in enumerate(t, 1):
	j.sort()
	for (k, (j, l)) in enumerate(j, 1):
		ans[l] = str(i).zfill(6) + str(k).zfill(6)
print('\n'.join(ans))


f = lambda : map(int, input().split())
(_, m) = f()
(d, t, c) = ({}, 0, 0)
for (p, y, i) in sorted((list(f()) + [i] for i in range(m))):
	if p > t:
		(t, c) = (p, 1)
	else:
		c += 1
	d[i] = str(p).zfill(6) + str(c).zfill(6)
for (_, v) in sorted(d.items()):
	print(v)


(N, M) = map(int, input().split())
dic = dict()
dic2 = dict()
P = list()
for i in range(M):
	(p, y) = map(int, input().split())
	if p not in dic.keys():
		dic[p] = [y]
	else:
		dic[p].append(y)
	P.append((p, y))
for key in dic.keys():
	dic[key].sort()
for key in dic.keys():
	for i in range(len(dic[key])):
		dic2[dic[key][i]] = i + 1
for i in range(M):
	(p, y) = P[i]
	ans = str(p).zfill(6) + str(dic2[y]).zfill(6)
	print(ans)


(n, m) = map(int, input().split())
pys = [0] * m
for i in range(m):
	(p, y) = map(int, input().split())
	pys[i] = (p, y, i)
pys.sort(key=lambda x: x[1])
cnt = [0] * n
ans = [0] * m
for (p, y, i) in pys:
	cnt[p - 1] += 1
	ans[i] = str(p).zfill(6) + str(cnt[p - 1]).zfill(6)
for i in ans:
	print(i)


from collections import defaultdict
(N, M) = map(int, input().split())
l = []
for i in range(M):
	(p, y) = map(int, input().split())
	l.append((y, p, i))
l.sort()
d = defaultdict(int)
c = []
for (y, p, i) in l:
	d[p] += 1
	c.append((i, str(p).zfill(6) + str(d[p]).zfill(6)))
c.sort()
for (i, x) in c:
	print(x)


(N, M) = map(int, input().split())
py = [list(map(int, input().split())) + [i] for i in range(M)]
py.sort()
P = py[0][0]
c = 0
ans = []
for (p, y, i) in py:
	if p == P:
		c += 1
	else:
		P = p
		c = 1
	ansc = str(c)
	ansp = str(p)
	anser = '0' * (6 - len(ansp)) + ansp + '0' * (6 - len(ansc)) + ansc
	ans.append([i, anser])
ans.sort()
for (i, anser) in ans:
	print(anser)


import collections
import bisect
(n, m) = map(int, input().split())
a = collections.defaultdict(list)
p = [[int(j) for j in input().split()] for i in range(m)]
for (x, y) in sorted(p):
	a[x] += [y]
for (x, y) in p:
	z = bisect.bisect(a[x], y)
	print('%06d%06d' % (x, z))


(N, M) = map(int, input().split())
l = [list(map(int, input().split())) + [i] for i in range(M)]
l = sorted(l, key=lambda x: x[0] * 1000000000 + x[1])
cnt = 0
for (i, x) in enumerate(l):
	if x[0] != l[i - 1][0]:
		cnt = 0
	cnt += 1
	l[i][1] = cnt
for x in sorted(l, key=lambda x: x[2]):
	print('{:06}{:06}'.format(x[0], x[1]))


(n, m) = map(int, input().split())
x = []
for i in range(m):
	(p, y) = map(int, input().split())
	x.append([y, p, i])
x.sort()
a = [0] * n
ans = [''] * m
for (y, p, i) in x:
	a[p - 1] += 1
	ans[i] = str(p).rjust(6, '0') + str(a[p - 1]).rjust(6, '0')
for i in ans:
	print(i)


import bisect
import collections
(N, M) = map(int, input().split())
L = collections.defaultdict(list)
p = [[int(j) for j in input().split()] for i in range(M)]
for (x, y) in sorted(p):
	L[x] += [y]
for (x, y) in p:
	z = bisect.bisect(L[x], y)
	print('%06d%06d' % (x, z))


I = lambda : list(map(int, input().split()))[::-1]
(m, n) = I()
c = [0] * -~n
a = [0] * m
for (y, p, i) in sorted((I() + [i] for i in range(m))):
	c[p] += 1
	a[i] = '%06d' % p + '%06d' % c[p]
for t in a:
	print(t)


import bisect
(n, m) = map(int, input().split())
py = [tuple(map(int, input().split())) for _ in range(m)]
t = [[] for _ in range(n)]
for (p, y) in py:
	t[p - 1].append(y)
for ti in t:
	ti.sort()
for (p, y) in py:
	kami = p
	shimo = bisect.bisect_left(t[p - 1], y) + 1
	print('{0:06d}{1:06d}'.format(kami, shimo))


from collections import defaultdict
import bisect
(n, m) = map(int, input().split())
PY = [list(map(int, input().split())) for _ in range(m)]
d = defaultdict(list)
for py in sorted(PY):
	d[py[0]].append(py[1])
for (p, y) in PY:
	print(str(p).zfill(6) + str(bisect.bisect_left(d[p], y) + 1).zfill(6))


(N, M) = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]
ans = [''] * M
num = [1] * N
for (i, v) in sorted(enumerate(X), key=lambda x: (x[1][0], x[1][1])):
	ans[i] = '{:06}{:06}'.format(v[0], num[v[0] - 1])
	num[v[0] - 1] += 1
print('\n'.join(ans))


(N, M) = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(M)]
now = 0
num = 0
d = dict()
for (p, y) in sorted(data):
	if now != p:
		now = p
		num = 1
	d[p, y] = num
	num += 1
for (p, y) in data:
	print('{:06d}{:06d}'.format(p, d[p, y]))


(N, M) = map(int, input().split())
pairs = []
for i in range(M):
	t = list(map(int, input().split()))
	pairs.append(t)
p_count = [1] * (N + 1)
for r in sorted(pairs, key=lambda x: x[1]):
	r.append('{:06d}{:06d}'.format(r[0], p_count[r[0]]))
	p_count[r[0]] += 1
print('\n'.join((r[2] for r in pairs)))


(N, M) = map(int, input().split())
X = [(0, 0, 0)] * M
Y = [1] * (N + 1)
for i in range(M):
	(p, y) = map(int, input().split())
	X[i] = (y, p, i)
X.sort()
ANS = [''] * M
for i in range(M):
	(y, p, j) = X[i]
	ans = '%06d' % p + '%06d' % Y[p]
	ANS[j] = ans
	Y[p] += 1
for i in range(M):
	print(ANS[i])


(N, M) = map(int, input().split())
cy = [1] * N
city = []
for i in range(M):
	(p, y) = map(int, input().split())
	city.append((y, p, i))
city.sort()
ans = [''] * M
for (y, p, i) in city:
	ans[i] = ('000000' + str(p))[-6:] + ('000000' + str(cy[p - 1]))[-6:]
	cy[p - 1] += 1
print(*ans, sep='\n')


(n, m) = map(int, input().split())
l = []
k = ['_'] * m
x = [1] * (n + 1)
for i in range(m):
	(a, b) = map(int, input().split())
	l.append([i, a, b])
y = sorted(l, key=lambda c: c[2])
for i in y:
	k[i[0]] = str(i[1]).zfill(6) + str(x[i[1]]).zfill(6)
	x[i[1]] += 1
for i in k:
	print(i)


import bisect
import collections
(N, M) = map(int, input().split())
q = [[int(j) for j in input().split()] for i in range(M)]
li = collections.defaultdict(list)
for (i, j) in sorted(q):
	li[i].append(j)
for (p, y) in q:
	z = bisect.bisect(li[p], y)
	print('{:0=6}'.format(p) + '{:0=6}'.format(z))


(N, M) = map(int, input().split())
PY = [list(map(int, input().split())) + [i] for i in range(M)]
PY = sorted(PY, key=lambda x: (x[0], x[1]))
k = 1
PY[0][1] = k
for i in range(1, M):
	if PY[i][0] != PY[i - 1][0]:
		k = 1
	else:
		k += 1
	PY[i][1] = k
PY = sorted(PY, key=lambda x: x[2])
for (p, y, _) in PY:
	print('{0:06}{1:06}'.format(p, y))


(n, m) = map(int, input().split())
ls = [[] for _ in range(n + 1)]
for i in range(m):
	(a, b) = map(int, input().split())
	ls[a].append((b, i))
ans = [None] * m
for (i, l) in enumerate(ls):
	l.sort()
	for (j, (a, b)) in enumerate(l):
		ans[b] = '{:06d}{:06d}'.format(i, j + 1)
for i in range(m):
	print(ans[i])


(N, M) = map(int, input().split())
D = [[] for i in range(N)]
for i in range(M):
	(p, y) = map(int, input().split())
	D[p - 1].append((y, i))
ans = [None] * M
for (i, d) in enumerate(D):
	d.sort()
	for (k, (y, j)) in enumerate(d):
		ans[j] = str(i + 1).zfill(6) + str(k + 1).zfill(6)
print(*ans, sep='\n')


import sys
import collections
import bisect as bs
input = sys.stdin.readline
(n, m) = map(int, input().split())
d = collections.defaultdict(list)
L = []
for i in range(m):
	(a, b) = map(int, input().split())
	L.append((a, b))
for (x, y) in sorted(L):
	d[x].append(y)
for (x, y) in L:
	z = bs.bisect(d[x], y)
	print('%06d%06d' % (x, z))


(n, m) = map(int, input().split())
D = [[] for _ in range(n)]
for i in range(m):
	(p, y) = map(int, input().split())
	D[p - 1].append((y, i))
ans = [None] * m
for (i, d) in enumerate(D):
	d.sort()
	for (j, (k, l)) in enumerate(d):
		ans[l] = str(i + 1).zfill(6) + str(j + 1).zfill(6)
for i in ans:
	print(i)


(N, M) = list(map(int, input().split()))
PY = [list(map(int, input().split())) + [i] for i in range(M)]
PY.sort(key=lambda x: x[1])
ans = []
cnt = [0] * N
for (p, y, i) in PY:
	ans.append(('{0:06d}'.format(p) + '{0:06d}'.format(cnt[p - 1] + 1), i))
	cnt[p - 1] += 1
ans.sort(key=lambda x: x[1])
for a in ans:
	print(a[0])


(n, m) = map(int, input().split())
a = [0] * (n + 1)
b = [list(map(int, input().split())) + [i] + [0] for i in range(m)]
b.sort(key=lambda x: x[1])
for (i, (x, y, l, z)) in enumerate(b):
	a[x - 1] += 1
	b[i][3] = a[x - 1]
b.sort(key=lambda x: x[2])
for (x, y, l, z) in b:
	print('{0:06d}{1:06d}'.format(x, z))


(N, M) = map(int, input().split())
PY = [list(map(int, input().split())) + [i] for i in range(M)]
PY.sort(key=lambda x: x[1])
num = [0] * N
w = [''] * M
for (p, y, i) in PY:
	num[p - 1] += 1
	w[i] = str(p).zfill(6) + str(num[p - 1]).zfill(6)
for i in range(M):
	print(w[i])


(n, m) = map(int, input().split())
pyi = [list(map(int, input().split())) + [i] for i in range(m)]
ids = [''] * m
s = {j + 1: 1 for j in range(n)}
for (p, y, i) in sorted(pyi, key=lambda d: d[1]):
	ids[i] = '%06d%06d' % (p, s[p])
	s[p] += 1
for iid in ids:
	print(iid)


(n, m) = map(int, input().split())
py = [list(map(int, input().split())) for i in range(m)]
c = [0] * n
sort_py = sorted(py, key=lambda x: x[1])
ans = dict()
for (p, y) in sort_py:
	c[p - 1] += 1
	ans[p, y] = str(p).zfill(6) + str(c[p - 1]).zfill(6)
for (p, y) in py:
	print(ans[p, y])


(N, M) = map(int, input().split())
cnt = [0] * N
history = []
res = [''] * M
for i in range(M):
	(P, Y) = map(int, input().split())
	history.append((Y, P - 1, i))
history.sort()
for i in range(M):
	cnt[history[i][1]] += 1
	res[history[i][2]] = str(history[i][1] + 1).zfill(6) + str(cnt[history[i][1]]).zfill(6)
for i in range(M):
	print(res[i])


(n, m) = map(int, input().split())
p = []
for i in range(m):
	(t1, t2) = map(int, input().split())
	p.append([i, t1, t2])
p.sort(key=lambda x: x[2])
c = [1 for i in range(n + 1)]
num = []
for (i, pre, yea) in p:
	tmp = str(pre).zfill(6) + str(c[pre]).zfill(6)
	num.append([i, tmp])
	c[pre] += 1
num.sort()
for i in num:
	print(i[1])


(n, m) = map(int, input().split())
PY = []
for _ in range(m):
	PY.append(list(map(int, input().split())))
sortedPY = sorted(PY, key=lambda x: x[1])
d = {}
o = [1] * (n + 1)
for i in sortedPY:
	d[i[0], i[1]] = o[i[0]]
	o[i[0]] += 1
for i in PY:
	print(str(i[0]).zfill(6) + str(d[i[0], i[1]]).zfill(6))


(N, M) = map(int, input().split())
P = [list(map(int, input().split())) for m in range(M)]
C = (N + 1) * [0]
D = {}
for (p, y) in sorted(P, key=lambda x: x[1]):
	C[p] += 1
	D[y] = '%06d%06d' % (p, C[p])
for (p, y) in P:
	print(D[y])


(n, m) = map(int, input().split())
PY = [list(map(int, input().split())) for _ in range(m)]
ypi = [[y, p, i] for (i, (p, y)) in enumerate(PY)]
ypi.sort()
from collections import defaultdict
d = defaultdict(int)
ans = [0] * m
for (y, p, i) in ypi:
	d[p] += 1
	ans[i] = str(p).zfill(6) + str(d[p]).zfill(6)
print(*ans, sep='\n')


from collections import defaultdict
(N, M) = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(M)]
d = defaultdict(int)
c = {}
for (p, y) in sorted(l, key=lambda x: x[1]):
	d[p] += 1
	c[y] = str(p).zfill(6) + str(d[p]).zfill(6)
for (p, y) in l:
	print(c[y])


(N, M) = map(int, input().split())
a = [[i] + list(map(int, input().split())) for i in range(M)]
a.sort(key=lambda x: (x[1], x[2]))
j = 0
for i in range(M):
	if j != a[i][1]:
		j = a[i][1]
		k = 1
	s = format(a[i][1], '0>6') + format(k, '0>6')
	a[i].append(s)
	k += 1
a.sort()
for i in range(M):
	print(a[i][3])


(n, m) = list(map(int, input().split()))
city = []
for i in range(m):
	a = list(map(int, input().split())) + [i]
	city.append(a)
city.sort(key=lambda x: x[1])
count = [1 for _ in range(n)]
for k in range(m):
	city[k].append(count[city[k][0] - 1])
	count[city[k][0] - 1] += 1
city.sort(key=lambda x: x[2])
for i in city:
	print(str(i[0]).zfill(6) + str(i[-1]).zfill(6))


import collections, bisect
(N, M) = map(int, input().split())
PY = [list(map(int, input().split())) for i in range(M)]
x = collections.defaultdict(list)
for (city, year) in sorted(PY):
	x[city] += [year]
for (city, year) in PY:
	num = bisect.bisect(x[city], year)
	print('%06d%06d' % (city, num))


(n, m) = list(map(int, input().split()))
p_y = []
for i in range(m):
	(p, y) = list(map(int, input().split()))
	p_y.append([p, y, i])
p_y_sorted = sorted(p_y)
li_id = []
prev_p = -1
cnt = 1
for i in p_y_sorted:
	if prev_p != i[0]:
		prev_p = i[0]
		cnt = 1
	id = str(i[0]).zfill(6) + str(cnt).zfill(6)
	li_id.append([i[2], id])
	cnt += 1
li_id_sorted = sorted(li_id)
for i in li_id_sorted:
	print(i[1])


import sys
input = sys.stdin.readline
(N, M) = [int(n) for n in input().split()]
lis = [[i] + [int(n) for n in input().split()] for i in range(M)]
l_2 = sorted(lis, key=lambda x: x[2])
dic = {}
for (k, i, j) in l_2:
	dic[i] = dic.get(i, 0) + 1
	lis[k] = '{:0=6}{:0=6}'.format(i, dic[i])
for i in lis:
	print(i)


def main():
	import sys
	input = sys.stdin.readline
	(N, M) = map(int, input().split())
	PY = [[i] + list(map(int, input().split())) for i in range(M)]
	PY = sorted(PY, key=lambda x: (x[1], x[2]))
	ans_li = ['0' * 12] * M
	town_dict = {}
	for (idx, p, y) in PY:
		x = town_dict.get(p, 1)
		id_ = ('{:6d}'.format(p) + '{:6d}'.format(x)).replace(' ', '0')
		ans_li[idx] = id_
		town_dict[p] = town_dict.get(p, 1) + 1
	print('\n'.join(ans_li))

def __starting_point():
	main()
__starting_point()


from collections import defaultdict
from bisect import bisect
(N, M) = map(int, input().split())
p = [tuple(map(int, input().split())) for _ in range(M)]
a = defaultdict(list)
for (x, y) in sorted(p):
	a[x] += [y]
for (x, y) in p:
	z = bisect(a[x], y)
	print('%06d%06d' % (x, z))


import numpy as np
(N, M) = map(int, input().strip().split())
PY = np.array([list(map(int, input().strip().split())) for _ in range(M)])
l = [[] for n in range(N)]
for m in range(M):
	l[PY[m, 0] - 1].append(PY[m, 1])
dp = {}
for n in range(N):
	if l[n]:
		l[n].sort()
		for i in range(len(l[n])):
			city = '000000' + str(n + 1)
			num = '000000' + str(i + 1)
			dp[n, l[n][i] - 1] = str(city[-6:] + num[-6:])
for m in range(M):
	print(dp[PY[m, 0] - 1, PY[m, 1] - 1])


from bisect import bisect_left
(n, m) = [int(i) for i in input().split()]
py = [[int(i) for i in input().split()] for _ in range(m)]
spy = list(sorted(py))
for (p, y) in py:
	l2 = bisect_left(spy, [p, y])
	l1 = bisect_left(spy, [p, 0])
	print(format(p, '06') + format(l2 - l1 + 1, '06'))


(N, M) = map(int, input().split())
P = [1] * N
C = [''] * M
PY = [[] for i in range(M)]
for i in range(M):
	(p, y) = map(int, input().split())
	PY[i] = [y, p, i]
PY.sort()
for (y, p, i) in PY:
	C[i] = ('0' * 6 + str(p))[-6:] + ('0' * 6 + str(P[p - 1]))[-6:]
	P[p - 1] += 1
for c in C:
	print(c)


(n, m) = map(int, input().split())
pyl = [[] for _ in range(n + 1)]
for i in range(m):
	(p, y) = map(int, input().split())
	pyl[p].append((y, i))
ans = [''] * m
for (p, yil) in enumerate(pyl):
	top = str(p).zfill(6)
	yil.sort()
	for (order, (y, i)) in enumerate(yil):
		bottom = order + 1
		bottom = str(bottom).zfill(6)
		ans[i] = top + bottom
for a in ans:
	print(a)


(n, m) = list(map(int, input().split()))
data = [tuple(map(int, input().split())) for _ in range(m)]
rank_map = {}
rank = 0
p = None
for t in sorted(data):
	if p != t[0]:
		p = t[0]
		rank = 1
	rank_map[t] = '%06d%06d' % (t[0], rank)
	rank += 1
for t in data:
	print(rank_map[t])


(N, M) = map(int, input().split())
l = []
for i in range(M):
	(P, Y) = map(int, input().split())
	l.append([i, P, Y, 0])
from operator import *
l.sort(key=itemgetter(2))
P = [0] * N
for i in range(M):
	P[l[i][1] - 1] += 1
	l[i][3] = P[l[i][1] - 1]
l.sort(key=itemgetter(0))
for i in range(M):
	print(str(l[i][1]).zfill(6) + str(l[i][3]).zfill(6))


import sys
from collections import defaultdict
((n, m), *q) = [[*list(map(int, i.split()))] for i in sys.stdin]
d = defaultdict(list)
for (k, v) in q:
	d[k].append(v)
c = defaultdict(dict)
for (k, v) in list(d.items()):
	for (i, j) in enumerate(sorted(v)):
		c[k][j] = i + 1
for (p, y) in q:
	print('{:0>6}{:0>6}'.format(p, c[p][y]))


(n, m) = map(int, input().split())
py = [list(map(int, input().split())) for i in range(m)]
ipy = [[0, 0, 0]]
for i in range(m):
	ipy.append([i] + py[i])
ipy = sorted(ipy, key=lambda x: (x[1], x[2]))
for i in range(1, m + 1):
	if ipy[i][1] != ipy[i - 1][1]:
		cnt = 0
	cnt += 1
	ipy[i].append(str(ipy[i][1]).zfill(6) + str(cnt).zfill(6))
ipy = sorted(ipy)
for i in range(1, m + 1):
	print(ipy[i][3])


import collections
import bisect
(N, M) = map(int, input().split())
P = [list(map(int, input().split())) for i in range(M)]
ans = collections.defaultdict(list)
for (p, y) in sorted(P):
	ans[p] += [y]
for (p, y) in P:
	print('%06d%06d' % (p, bisect.bisect(ans[p], y)))


(N, M) = map(int, input().split())
D = [[] for _ in range(N)]
R = [0] * M
for i in range(M):
	(P, Y) = map(int, input().split())
	D[P - 1].append((Y, i))
for P in range(N):
	for (k, p) in enumerate(sorted(D[P])):
		(Y, i) = p
		R[i] = (P + 1) * 10 ** 6 + (k + 1)
for r in R:
	print('{:012}'.format(r))


(n, m) = map(int, input().split())
D = [[] for i in range(n)]
for i in range(m):
	(p, y) = map(int, input().split())
	D[p - 1].append((y, i))
ans = [0] * m
for (i, d) in enumerate(D):
	d.sort()
	for (k, (y, j)) in enumerate(d):
		ans[j] = str(i + 1).zfill(6) + str(k + 1).zfill(6)
print(*ans, sep='\n')


(n, m) = map(int, input().split())
a = []
b = [[] for i in range(n)]
for i in range(m):
	(p, y) = map(int, input().split())
	a.append([p, y])
	b[p - 1].append(y)
dic = {}
for i in range(n):
	b[i].sort()
	for (j, k) in enumerate(b[i]):
		dic[k] = j + 1
for (i, j) in a:
	print('{:06d}'.format(i) + '{:06d}'.format(dic[j]))


(N, M) = map(int, input().split())
PY = [tuple(map(int, input().split())) for _ in range(M)]
sPY = sorted(PY, key=lambda py: (py[0], py[1]))
i = 1
bp = 1
d = {}
for (p, y) in sPY:
	if p != bp:
		i = 1
		bp = p
	d[y] = i
	i += 1
for (p, y) in PY:
	print('{0:06}{1:06}'.format(p, d[y]))


(n, m) = map(int, input().split())
py = [list(map(int, input().split())) for i in range(m)]
c = [0] * (n + 1)
id = {}
for (p, y) in sorted(py, key=lambda x: x[1]):
	c[p] += 1
	id[y] = format(p, '06') + format(c[p], '06')
for (p, y) in py:
	print(id[y])


(n, m) = map(int, input().split())
p_dict = {}
ans = []
for i in range(m):
	(p, y) = map(int, input().split())
	if p not in p_dict.keys():
		p_dict[p] = [[y, p, i]]
	else:
		p_dict[p].append([y, p, i])
for p in p_dict.keys():
	p_dict[p].sort()
	for i in range(len(p_dict[p])):
		p_dict[p][i].append(i + 1)
		ans.append(p_dict[p][i])
ans.sort(key=lambda x: x[2])
for (y, p, oi, si) in ans:
	print('{:06d}{:06d}'.format(p, si))


(n, m) = map(int, input().split())
citylis = [[] for i in range(n)]
for i in range(1, m + 1):
	(pi, yi) = map(int, input().split())
	citylis[pi - 1].append([i, yi])
for i in range(n):
	if len(citylis[i]) != 0:
		citylis[i].sort(key=lambda x: x[1])
lis = []
for i in range(n):
	for j in range(len(citylis[i])):
		cityposi = str(i + 1)
		cityposi = '0' * (6 - len(cityposi)) + cityposi
		ordernum = str(j + 1)
		ordernum = '0' * (6 - len(ordernum)) + ordernum
		lis.append([citylis[i][j][0], cityposi + ordernum])
lis.sort(key=lambda x: x[0])
for i in range(m):
	print(lis[i][1])


(N, M) = map(int, input().split())
list = [[] for i in range(N)]
for i in range(M):
	(j, k) = map(int, input().split())
	list[j - 1].append((k, i))
ans = [None] * M
for (i, j) in enumerate(list):
	j.sort()
	for (k, (l, m)) in enumerate(j):
		ans[m] = '%06d%06d' % (i + 1, k + 1)
print(*ans, sep='\n')


(n, m) = map(int, input().split())
py = [list(map(int, input().split())) + [i] for i in range(m)]
py.sort(key=lambda x: [x[0], x[1]])
ans = []
P = [0] * (n + 1)
for (p, y, i) in py:
	P[p] += 1
	tmp = str(p).zfill(6) + str(P[p]).zfill(6)
	ans.append([i, tmp])
ans.sort()
for (i, a) in ans:
	print(a)


(N, M) = list(map(int, input().split()))
PY = [[list(map(int, input().split())), i] for i in range(M)]
PY.sort()
cnt = [0 for i in range(N + 1)]
ans = []
for i in range(M):
	cnt[PY[i][0][0]] += 1
	ans.append([PY[i][1], str(PY[i][0][0]).zfill(6) + str(cnt[PY[i][0][0]]).zfill(6)])
ans.sort()
for i in range(M):
	print(ans[i][1])


(n, m) = map(int, input().split())
l = [[] for i in range(n)]
for i in range(m):
	(p, y) = map(int, input().split())
	l[p - 1].append((y, i))
ids = ['' for i in range(m)]
for i in range(n):
	l[i].sort()
	for j in range(len(l[i])):
		ids[l[i][j][1]] = '{:0>6d}'.format(i + 1) + '{:0>6d}'.format(j + 1)
print('\n'.join(ids))


(n, m) = map(int, input().split())
import bisect
l = [[] for _ in range(n)]
l2 = []
for i in range(m):
	(p, y) = map(int, input().split())
	l[p - 1].append(y)
	l2.append([p, y])
for m in l:
	m.sort()
for m in l2:
	print('{:06d}'.format(m[0]) + '{:06d}'.format(bisect.bisect_left(l[m[0] - 1], m[1]) + 1))


(N, M) = map(int, input().split())
PY = [list(map(int, input().split())) for _ in range(M)]
for i in range(M):
	PY[i].append(i)
PY.sort(key=lambda x: x[1])
ans = [0] * M
num = [0] * N
for (p, y, i) in PY:
	ans[i] = str(p).zfill(6) + str(num[p - 1] + 1).zfill(6)
	num[p - 1] += 1
for s in ans:
	print(s)


import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
input = sys.stdin.readline

def RD():
	return input().rstrip()

def F():
	return float(input().rstrip())

def I():
	return int(input().rstrip())

def MI():
	return map(int, input().split())

def MF():
	return map(float, input().split())

def LI():
	return list(map(int, input().split()))

def TI():
	return tuple(map(int, input().split()))

def LF():
	return list(map(float, input().split()))

def Init(H, W, num):
	return [[num for i in range(W)] for j in range(H)]

def main():
	(N, M) = MI()
	L = []
	for i in range(M):
		temp = [i] + LI()
		L.append(temp)
	L.sort(key=lambda x: x[2])
	L.sort(key=lambda x: x[1])
	ans = [0] * M
	D = defaultdict(int)
	for (a, b, c) in L:
		D[b] += 1
		c = D[b]
		ans[a] = str(b).zfill(6) + str(c).zfill(6)
	for i in ans:
		print(i)

def __starting_point():
	main()
__starting_point()


(N, M) = map(int, input().split())
yi = [[] for i in range(N)]
for i in range(M):
	(pp, yy) = map(int, input().split())
	yi[pp - 1].append((yy, i))
code = ['' for _ in range(M)]
for (pp, d) in enumerate(yi):
	d.sort()
	for (x, (yy, i)) in enumerate(d):
		code[i] = '%06d%06d' % (pp + 1, x + 1)
print(*code, sep='\n')


(N, M) = list(map(int, input().split()))
keep = [[] for i in range(N)]
keep2 = []
for i in range(M):
	(p, y) = list(map(int, input().split()))
	keep[p - 1].append([i, p, y])
for i in range(N):
	keep[i] = sorted(keep[i], key=lambda x: x[2])
for i in range(N):
	biggest = len(keep[i])
	j = 0
	while j < biggest:
		keep[i][j][2] = j + 1
		j += 1
	keep2 += keep[i]
keep2 = sorted(keep2, key=lambda x: x[0])
for i in range(M):
	ans = ''
	ans += '0' * (6 - len(str(keep2[i][1]))) + str(keep2[i][1])
	ans += '0' * (6 - len(str(keep2[i][2]))) + str(keep2[i][2])
	print(ans)


(n, m) = map(int, input().split())
order = [1] * n
ans = [''] * m
PY = []
for i in range(m):
	(p, y) = map(int, input().split())
	PY.append((y, p, i))
PY.sort()
for (y, p, i) in PY:
	s_p = str(p).zfill(6)
	y_p = str(order[p - 1]).zfill(6)
	order[p - 1] += 1
	ans[i] = s_p + y_p
for i in ans:
	print(i)


(n, m) = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(m)]
l2 = sorted(l, key=lambda x: x[1])
d = dict()
for (p, y) in l2:
	if not p in d.keys():
		d[p] = dict()
	d[p][y] = len(d[p]) + 1
for (p, y) in l:
	print('{}'.format(p).zfill(6) + '{}'.format(d[p][y]).zfill(6))


(N, M) = map(int, input().split())
arr = []
for i in range(M):
	(p, y) = map(int, input().split())
	arr.append((p, y, i))
arr.sort()
ans = {}
prev = None
tmp = None
for (p, y, i) in arr:
	if prev == None or p != prev:
		tmp = 1
	ans[i] = '%06d%06d' % (p, tmp)
	tmp += 1
	prev = p
for i in range(M):
	print(ans[i])


from collections import defaultdict
import bisect
(N, M) = map(int, input().split())
dic = defaultdict(list)
cities = []
for _ in range(M):
	(p, y) = map(int, input().split())
	cities.append([p, y])
for item in sorted(cities):
	dic[item[0]].append(item[1])
for item in cities:
	print('%06d%06d' % (item[0], bisect.bisect(dic[item[0]], item[1])))


from collections import deque
(n, m) = list(map(int, input().split()))
prefs = [{} for _ in range(n)]
cities = deque()
for i in range(m):
	(p, y) = list(map(int, input().split()))
	prefs[p - 1][y] = -1
	cities.append((p, y))
for p in prefs:
	years = list(p.keys())
	years.sort()
	for y in range(len(years)):
		p[years[y]] = y + 1
for _ in range(m):
	(p, y) = cities.popleft()
	cid = prefs[p - 1][y] + p * 1000000
	print('{:0=12}'.format(cid))


(n, m) = list(map(int, input().split()))
c = [0] * (n + 1)
py = []
for i in range(m):
	py.append(list(map(int, input().split())) + [i])
py.sort(key=lambda x: x[1])
a = [''] * m
for (p, y, i) in py:
	c[p] += 1
	x = c[p]
	z = str(p * 1000000 + x)
	if len(z) < 12:
		a[i] = '0' * (12 - len(z)) + z
	else:
		a[i] = z
for x in a:
	print(x)


(N, M) = map(int, input().split())
citys = [list(map(int, input().split())) + [i] for i in range(M)]
citys.sort(key=lambda x: x[1])
nums = [0] * (N + 1)
states = [None] * M
for (p, y, i) in citys:
	nums[p] += 1
	states[i] = [str(p), str(nums[p])]
for s in states:
	print(s[0].zfill(6) + s[1].zfill(6))


import bisect
import heapq
(n, m) = map(int, input().split())
py_i = [[int(x) for x in input().split()] for _ in range(m)]
y_p = [[] for i in range(n + 1)]
for (x, y) in sorted(py_i):
	y_p[x].append(y)
for (x, y) in py_i:
	z = bisect.bisect_right(y_p[x], y)
	print('%06d' % x + '%06d' % z)


(n, m) = map(int, input().split())
py = [list(map(int, input().split())) for _ in range(m)]
pysort = sorted(py, key=lambda val: val[1])
(pcnt, ans_d) = ([0] * (10 ** 5 + 1), {})
for (i, j) in pysort:
	pcnt[i] += 1
	ans_d[j] = str(pcnt[i])
for (i, j) in py:
	print(str(i).zfill(6) + ans_d[j].zfill(6))


(n, m) = map(int, input().split())
py = [list(map(int, input().split())) + [i] for i in range(m)]
py.sort(key=lambda x: x[0] * 10 ** 6 + x[1])
ne = [1] * (10 ** 5 + 1)
ans = []
for (p, _, i) in py:
	ans.append((str(p).zfill(6) + str(ne[p]).zfill(6), i))
	ne[p] += 1
ans.sort(key=lambda x: x[1])
for (s, _) in ans:
	print(s)


(_, m) = map(int, input().split())
ta = [list(map(int, input().split())) + [i] for i in range(m)]
a = sorted(ta)
ans = [-1] * m
j = 0
for i in range(m):
	if j != a[i][0]:
		j = a[i][0]
		k = 1
	p = str(a[i][0]).zfill(6) + str(k).zfill(6)
	ans[a[i][2]] = p
	k += 1
a.sort()
for i in range(m):
	print(ans[i])


(N, M) = map(int, input().split())
a = []
for i in range(M):
	(n, m) = map(int, input().split())
	a.append([n, m, i])
ans = ['0'] * M
a.sort()
j = 0
for i in range(M):
	if j != a[i][0]:
		j = a[i][0]
		c = 1
	ans[a[i][2]] = str(a[i][0]).zfill(6) + str(c).zfill(6)
	c += 1
for i in range(M):
	print(ans[i])


(n, m) = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(m)]
B = A[:]
A.sort()
cnt = 0
prev = 0
ans = dict()
for (p, y) in A:
	if prev != p:
		cnt = 1
		prev = p
	ans[p, y] = '{0:06d}{1:06d}'.format(p, cnt)
	cnt += 1
for (p, y) in B:
	print(ans[p, y])


(N, M) = list(map(int, input().split()))
PY = [list(map(int, input().split())) + [i, 0] for i in range(M)]
d = {}
for i in sorted(PY, key=lambda x: x[1]):
	if i[0] in d:
		d[i[0]] += 1
	else:
		d[i[0]] = 1
	i[3] = d[i[0]]
for i in PY:
	print(str(i[0]).zfill(6) + str(i[3]).zfill(6))


(n, m) = map(int, input().split())
PY = []
for i in range(m):
	(p, y) = map(int, input().split())
	PY.append([y, p, i])
PY.sort()
pre = [0] * n
citys = [''] * m
for (y, p, i) in PY:
	pre[p - 1] += 1
	citys[i] = str(p).zfill(6) + str(pre[p - 1]).zfill(6)
for city in citys:
	print(city)


(n, m) = map(int, input().split())
C = [[i] + list(map(int, input().split())) for i in range(m)]
C.sort(key=lambda c: c[1:])
prev = 0
count = 0
for c in C:
	if prev == c[1]:
		count += 1
	else:
		count = 1
	c.append(format(c[1], '0>6') + format(count, '0>6'))
	prev = c[1]
for c in sorted(C, key=lambda c: c[0]):
	print(c[3])


I = lambda : list(map(int, input().split()))
(n, m) = I()
a = [[i] + I() for i in range(m)]
a = sorted(a, key=lambda x: (x[1], x[2]))
b = []
j0 = 0
p = 1
for (i, j, k) in a:
	if j != j0:
		p = 1
	else:
		p += 1
	b.append([i, j, p])
	j0 = j
b = sorted(b, key=lambda x: x[0])
for (i, j, k) in b:
	print('{:06d}{:06d}'.format(j, k))


import collections
import bisect
(n, m) = map(int, input().split())
s = [[int(_) for _ in input().split()] for _ in range(m)]
a = collections.defaultdict(list)
for (x, y) in sorted(s):
	a[x] += [y]
for (x, y) in s:
	z = bisect.bisect(a[x], y)
	print('%06d%06d' % (x, z))


from collections import defaultdict
from bisect import bisect
(n, m) = map(int, input().split())
l = [tuple(map(int, input().split())) for _ in range(m)]
a = defaultdict(list)
for (x, y) in sorted(l):
	a[x] += [y]
for (x, y) in l:
	z = bisect(a[x], y)
	print('%06d%06d' % (x, z))


(n, m) = map(int, input().split())
ls = [[] for _ in range(n + 1)]
di = []
for i in range(m):
	(a, b) = map(int, input().split())
	ls[a].append([b, i + 1])
for j in range(n + 1):
	if ls[j] != []:
		ls[j].sort(key=lambda x: x[0])
		for k in range(len(ls[j])):
			di.append([ls[j][k][1], str(10 ** 12 + j * 10 ** 6 + k + 1)[1:]])
di.sort(key=lambda x: x[0])
for l in range(m):
	print(di[l][1])


(N, M) = map(int, input().split())
PY = []
for i in range(M):
	PY.append(list(map(int, input().split())))
cnt = [1] * (N + 1)
for j in sorted(PY, key=lambda x: x[1]):
	j.append('{:06d}{:06d}'.format(j[0], cnt[j[0]]))
	cnt[j[0]] += 1
for k in PY:
	print(k[2])


(n, m) = list(map(int, input().split()))
ps = [[] for _ in range(n)]
for i in range(m):
	(p, y) = list(map(int, input().split()))
	ps[p - 1].append((y, i))
for i in range(n):
	ps[i] = sorted(ps[i])
	pstr = str(i + 1).zfill(6)
	for j in range(len(ps[i])):
		ps[i][j] = (pstr + str(j + 1).zfill(6), ps[i][j][1])
ps = [city for sub in ps for city in sub]
ps = sorted(ps, key=lambda x: x[1])
for city in ps:
	print(city[0])


def main():
	import bisect
	(n, m) = list(map(int, input().split()))
	d = [[] for i in range(n)]
	ans = [0 for i in range(m)]
	for i in range(m):
		(p, y) = list(map(int, input().split()))
		d[p - 1].append((y, i))
	for (i, d_) in enumerate(d):
		d_.sort()
		for (c, d__) in enumerate(d_):
			ans[d__[1]] = str(i + 1).zfill(6) + str(c + 1).zfill(6)
	for i in range(m):
		print(ans[i])

def __starting_point():
	main()
__starting_point()


(N, M) = map(int, input().split())
P = [list(map(int, input().split())) for i in range(M)]
for i in range(M):
	P[i].append(i)
P.sort(key=lambda x: x[1])
B = [1] * N
for i in range(M):
	P[i] += ('0' * (6 - len(str(P[i][0]))) + str(P[i][0]) + '0' * (6 - len(str(B[P[i][0] - 1]))) + str(B[P[i][0] - 1]),)
	B[P[i][0] - 1] += 1
P.sort(key=lambda x: x[2])
for i in range(M):
	print(P[i][3])


(n, m) = list(map(int, input().split()))
city = [list(map(int, input().split())) for _ in range(m)]
pref = [[] for _ in range(n + 1)]
ans = []
for (i, c) in enumerate(city):
	pref[c[0]].append([i, c[1]])
for i in range(n):
	pref[i + 1].sort(key=lambda x: x[1])
	for j in range(len(pref[i + 1])):
		ans.append([pref[i + 1][j][0], str(i + 1).zfill(6) + str(j + 1).zfill(6)])
ans.sort(key=lambda x: x[0])
for c in ans:
	print(c[1])


(N, M) = list(map(int, input().split()))
P = [0] * M
for i in range(M):
	P[i] = list(map(int, input().split())) + [i + 1]
P = sorted(P, key=lambda x: x[1])
P = sorted(P, key=lambda x: x[0])
a = P[0][0]
c = 0
for i in range(M):
	if P[i][0] == a:
		c += 1
		P[i].append(c)
	else:
		c = 1
		a = P[i][0]
		P[i].append(c)
P = sorted(P, key=lambda x: x[2])
for i in range(M):
	s = str(P[i][0]).zfill(6)
	ss = str(P[i][3]).zfill(6)
	print(s + ss)


class City:

	def __init__(self, prefecture, year):
		self.prefecture = prefecture
		self.year = year
		self.order = None

	def __eq__(self, other):
		if self.year == other.year:
			return True
		return False

	def __le__(self, other):
		if self.year <= other.year:
			return True
		return False

	def __lt__(self, other):
		if self.year < other.year:
			return True
		return False

	def __ge__(self, other):
		if self.year >= other.year:
			return True
		return False

	def __gt__(self, other):
		if self.year > other.year:
			return True
		return False
cities = []
(n, m) = [int(i) for i in input().split()]
prefecture = [[] for i in range(n + 1)]
for i in range(m):
	(p, y) = [int(j) for j in input().split()]
	new_city = City(p, y)
	cities.append(new_city)
	prefecture[p].append(new_city)
for pref_list in prefecture:
	pref_list.sort()
	for (i, pref) in enumerate(pref_list):
		pref.order = i + 1
for city in cities:
	print(str(city.prefecture).zfill(6) + str(city.order).zfill(6))


from collections import defaultdict
from bisect import bisect_right
dic_PY = defaultdict(list)
(N, M) = map(int, input().split())
PY = [list(map(int, input().split())) for _ in range(M)]
for (p, y) in sorted(PY):
	dic_PY[p] += [y]
for (p, y) in PY:
	z = bisect_right(dic_PY[p], y)
	print('%06d%06d' % (p, z))


(n, m) = map(int, input().split())
L = [tuple(map(int, input().split())) for _ in range(m)]
cnt = [0] * (n + 1)
IDs = {}
for (p, y) in sorted(L, key=lambda x: x[1]):
	cnt[p] += 1
	IDs[y] = '%06d%06d' % (p, cnt[p])
for (_, y) in L:
	print(IDs[y])


(n, m) = map(int, input().split())
numbers = [{} for _ in range(n)]
for i in range(m):
	(p, y) = map(int, input().split())
	numbers[p - 1][i] = y
answers = {}
for i in range(n):
	number = numbers[i]
	if len(number) == 0:
		continue
	new_number = sorted(number.items(), key=lambda x: x[1])
	cnt = 1
	for num in new_number:
		answers[num[0]] = (6 - len(str(i + 1))) * '0' + str(i + 1) + (6 - len(str(cnt))) * '0' + str(cnt)
		cnt += 1
answer = sorted(answers.items(), key=lambda x: x[0])
for i in answer:
	print(i[1])


(N, M) = map(int, input().split())
list = [[] for i in range(N)]
for i in range(M):
	(p, y) = map(int, input().split())
	list[p - 1].append((y, i))
ans = [None] * M
for (j, list_p) in enumerate(list):
	list_p.sort()
	for (k, (p, y)) in enumerate(list_p):
		ans[y] = '%06d%06d' % (j + 1, k + 1)
print(*ans, sep='\n')


(N, M) = map(int, input().split())
PY = [tuple(map(int, input().split())) for _ in range(M)]
ans = [None] * M
I = sorted(range(M), key=lambda i: PY[i][1])
C = [0] * (N + 1)
for i in I:
	p = PY[i][0]
	C[p] += 1
	ans[i] = (p, C[p])

def f(x):
	s = str(x)
	return '0' * (6 - len(s)) + s
for (p, c) in ans:
	print(f(p) + f(c))


import bisect
from collections import defaultdict
(n, m) = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(m)]
a = defaultdict(list)
for (x, y) in sorted(p):
	a[x].append(y)
for (x, y) in p:
	z = bisect.bisect(a[x], y)
	print('{0:06d}{1:06d}'.format(x, z))


(N, M) = map(int, input().split())
(P, Y) = zip(*(map(int, input().split()) for _ in range(M)))
ans = ['' for _ in range(M)]
c = [1 for _ in range(N + 1)]
for (i, t) in sorted(enumerate(zip(P, Y)), key=lambda x: x[1][1]):
	ans[i] = '{:06}{:06}'.format(t[0], c[t[0]])
	c[t[0]] += 1
print('\n'.join(ans))


(N, M) = [int(_) for _ in input().split()]
PY = [[i] + [int(_) for _ in input().split()] + [0] for i in range(M)]
nums = [1] * (N + 1)
PY.sort(key=lambda x: x[2])
for row in PY:
	y = row[1]
	row[3] = nums[y]
	nums[y] += 1
PY.sort(key=lambda x: x[0])
for row in PY:
	print('%06d%06d' % (row[1], row[3]))


def __starting_point():
	(n, m) = list(map(int, input().split()))
	A = []
	for i in range(m):
		(a, b) = list(map(int, input().split()))
		A.append([a, b, i, ''])
	B = sorted(A, key=lambda x: (x[0], x[1]))
	no = 1
	tmp = 0
	for b in B:
		if tmp == b[0]:
			no += 1
		else:
			tmp = b[0]
			no = 1
		cityno = str(b[0]).zfill(6) + str(no).zfill(6)
		b[3] = cityno
	C = sorted(B, key=lambda x: x[2])
	for c in C:
		print(c[3])
__starting_point()


(N, M) = map(int, input().split())
PY = [list(map(int, input().split())) for _ in range(M)]
iPY = [[i] + PY[i] for i in range(M)]
iPY.sort(key=lambda x: (x[1], x[2]))
ans = []
cnt = 1
last = -1
for (i, p, y) in iPY:
	if p == last:
		cnt += 1
	else:
		last = p
		cnt = 1
	ans.append([i, str(p).zfill(6) + str(cnt).zfill(6)])
ans.sort()
for a in ans:
	print(a[1])


def main():
	(n, m) = map(int, input().split())
	l = [tuple(map(int, input().split())) for _ in range(m)]
	py = sorted(l, key=lambda x: (x[0], x[1]))
	d = {}
	i = 1
	prev = 0
	for (p, y) in py:
		if prev != p:
			i = 1
			prev = p
		d[p, y] = '{:0>6}'.format(p) + '{:0>6}'.format(i)
		i += 1
	for x in l:
		print(d[x])

def __starting_point():
	main()
__starting_point()


(n, m) = map(int, input().split())
PY = [list(map(int, input().split())) for _ in range(m)]
for i in range(m):
	PY[i].append(i)
py = sorted(PY)
ans = [None] * m
tmp_y = 1
for i in range(m):
	if i > 0:
		if py[i][0] != py[i - 1][0]:
			tmp_y = 1
		else:
			tmp_y += 1
	ans_l = '0' * (6 - len(str(py[i][0]))) + str(py[i][0])
	ans_r = '0' * (6 - len(str(tmp_y))) + str(tmp_y)
	ans[py[i][2]] = ans_l + ans_r
[print(i) for i in ans]


(n, m) = [int(i) for i in input().split()]
py = []
for j in range(m):
	py.append([j] + [int(i) for i in input().split()])
py.sort(key=lambda x: x[2])
b = [1] * n
c = []
for i in py:
	c.append([str(i[1]).zfill(6) + str(b[i[1] - 1]).zfill(6), i[0]])
	b[i[1] - 1] += 1
c.sort(key=lambda x: x[1])
for i in c:
	print(i[0])


(n, m) = map(int, input().split())
L = []
for i in range(m):
	li = list(map(int, input().split()))
	L.append(li)
li = []
for (i, j) in enumerate(L):
	li.append(j + [i])
li.sort(key=lambda x: (x[0], x[1]))
li.append([0, 0, 0])
(k, r) = (li[0][0], 1)
for i in range(m):
	if li[i][0] == k:
		if li[i + 1][1] == li[i][1]:
			li[i][1] = r
			li[i + 1][1] = r
		else:
			li[i][1] = r
			r += 1
	else:
		k = li[i][0]
		r = 1
		li[i][1] = r
		r += 1
li.pop()
li.sort(key=lambda x: x[2])
for i in range(m):
	print('{:06d}'.format(li[i][0]) + '{:06d}'.format(li[i][1]))


(N, M) = map(int, input().split())
mp = {}
for i in range(M):
	(P, Y) = map(int, input().split())
	if not P in mp:
		mp[P] = []
	mp[P].append((Y, i))
res = [''] * M
for (k, li) in sorted(mp.items()):
	for (i, (y, l)) in enumerate(sorted(li)):
		res[l] = '{:06d}{:06d}'.format(k, i + 1)
for st in res:
	print(st)


(n, m) = (int(i) for i in input().split())
p = [[int(i) for i in input().split()] for i in range(m)]
c = [0] * n
i = {}
for (pe, pk) in sorted(p, key=lambda x: x[1]):
	c[pe - 1] += 1
	i[pk] = '%06d%06d' % (pe, c[pe - 1])
for (_, pk) in p:
	print(i[pk])


from collections import defaultdict
(N, M) = map(int, input().split())
years = [tuple(map(int, input().split())) for _ in range(M)]
d = defaultdict(int)
b = dict()
for (p, y) in sorted(years, key=lambda x: x[1]):
	d[p] += 1
	b[y] = '{:06d}{:06d}'.format(p, d[p])
for (p, y) in years:
	print(b[y])


import bisect
(n, m) = map(int, input().split())
x = [list() for i in range(n)]
p = []
y = []
for i in range(m):
	(s, t) = map(int, input().split())
	p.append(s)
	y.append(t)
	x[s - 1].append(t)
for i in range(n):
	x[i].sort()
for i in range(m):
	index = bisect.bisect_left(x[p[i] - 1], y[i])
	print('{:06}{:06}'.format(p[i], index + 1))


(n, m) = map(int, input().split())
N = [1] * n
D = []
for i in range(m):
	(p, y) = map(int, input().split())
	D.append([i, p, y])
D.sort(key=lambda x: x[2])
for i in range(m):
	D[i].append(N[D[i][1] - 1])
	N[D[i][1] - 1] += 1
D.sort()
for d in D:
	print('{:0>6}{:0>6}'.format(d[1], d[3]))


(N, M) = map(int, input().split())
p = [[] for i in range(M)]
counter = [0] * N
ans = [''] * M
for i in range(M):
	(k, y) = map(int, input().split())
	p[i] = [k, y, i]
p.sort(key=lambda x: x[1])
for (k, y, i) in p:
	counter[k - 1] += 1
	ans[i] = '{:06d}{:06d}'.format(k, counter[k - 1])
for i in ans:
	print(i)


(n, m) = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
for i in range(m):
	ab[i].append(i)
ab_l = sorted(ab, key=lambda x: x[1])
ab_ll = sorted(ab_l, key=lambda x: x[0])
temp = 1
for j in range(m):
	if j == 0 or ab_ll[j][0] != ab_ll[j - 1][0]:
		temp = 1
	else:
		temp += 1
	ab_ll[j].append(temp)
ab_lll = sorted(ab_ll, key=lambda x: x[2])
for i in range(m):
	print(str(ab_lll[i][0]).zfill(6) + str(ab_lll[i][3]).zfill(6))


(N, M) = map(int, input().split())
P = []
for _ in range(M):
	(p, y) = map(int, input().split())
	P.append((p, y))
d = {}
for (p, y) in P:
	if p not in d:
		d[p] = []
	d[p].append(y)
sd = {k: dict(zip(sorted(v), range(1, 1 + len(v)))) for (k, v) in d.items()}
for (p, y) in P:
	print('%06d%06d' % (p, sd[p][y]))


(n, m) = map(int, input().split())
P = []
for i in range(m):
	(p, y) = map(int, input().split())
	P.append([p, y, i])
nums = [0] * n
ans = [''] * m
P.sort(key=lambda x: x[1])
for (p, y, i) in P:
	nums[p - 1] += 1
	ans[i] = (6 - len(str(p))) * '0' + str(p) + (6 - len(str(nums[p - 1]))) * '0' + str(nums[p - 1])
for an in ans:
	print(an)


(n, m) = map(int, input().split())
py = [[i + 1] + list(map(int, input().split())) for i in range(m)]
pysort = sorted(py, key=lambda x: (x[1], x[2]))
j = 1
cnt = 0
for i in range(m):
	while True:
		if pysort[i][1] == j:
			cnt += 1
			pysort[i] += [str(pysort[i][1]).zfill(6) + str(cnt).zfill(6)]
			break
		else:
			cnt = 0
			j += 1
pysortsort = sorted(pysort, key=lambda x: x[0])
[print(a[3]) for a in pysortsort]


(N, M) = map(int, input().split())
py = sorted([list(map(int, input().split())) + [i] for i in range(M)], key=lambda x: x[1])
count = [1] * N
ans = [None] * M
for i in range(M):
	(p, y, num) = py[i]
	ans[num] = '{:0>6}{:0>6}'.format(p, count[p - 1])
	count[p - 1] += 1
for i in range(M):
	print(ans[i])


(n, m) = list(map(int, input().split()))
order = [[] for i in range(n + 1)]
id_perf_map = [-1 for i in range(m + 1)]
for i in range(1, m + 1):
	(p, y) = list(map(int, input().split()))
	id_perf_map[i] = p
	order[p].append((i, y))
id_num_map = [-1 for i in range(m + 1)]
for i in range(1, n + 1):
	order[i] = list(sorted(order[i], key=lambda x: x[1]))
	for (idx, (city_id, _)) in enumerate(order[i]):
		id_num_map[city_id] = idx + 1
for i in range(1, m + 1):
	print('{:06}{:06}'.format(id_perf_map[i], id_num_map[i]))


(N, M) = map(int, input().split())
py = [list(map(int, input().split())) for _ in range(M)]
epy = list(enumerate(py))
P = [[] for _ in range(N + 1)]
for x in epy:
	P[x[1][0]].append(x)
i = 1
ans = []
while i <= N:
	L = P[i]
	L.sort(key=lambda x: x[1])
	j = 0
	while j < len(L):
		L[j][1][1] = j + 1
		ans.append(L[j])
		j += 1
	i += 1
ans.sort()
for (e, py) in ans:
	(p, y) = map(str, py)
	p = '0' * (6 - len(p)) + p
	y = '0' * (6 - len(y)) + y
	print(p + y)


import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda : sys.stdin.readline().strip()
NI = lambda : int(input())
NMI = lambda : map(int, input().split())
NLI = lambda : list(NMI())
SI = lambda : input()

def main():
	(N, M) = NMI()
	PY = [[m, NLI()] for m in range(M)]
	PY = list(sorted(list(sorted(PY, key=lambda x: x[1][1])), key=lambda x: x[1][0]))
	city = PY[0][1][0]
	cnt = 0
	for m in range(M):
		if PY[m][1][0] == city:
			cnt += 1
		else:
			city = PY[m][1][0]
			cnt = 1
		PY[m][1] = str(PY[m][1][0]).zfill(6) + str(cnt).zfill(6)
	PY = list(sorted(PY))
	for m in range(M):
		print(PY[m][1])

def __starting_point():
	main()
__starting_point()


(n, m) = map(int, input().split())
x = [[] for _ in range(n + 1)]
ans = [-1] * m
for i in range(m):
	(p, y) = map(int, input().split())
	x[p].append([y, i])
for p in range(1, n + 1):
	x[p].sort()
	for j in range(len(x[p])):
		ans[x[p][j][1]] = str(p).zfill(6) + str(j + 1).zfill(6)
for i in range(m):
	print(ans[i])


def digit6(n):
	return ('000000' + str(n))[-6:]

def main():
	(N, M) = list(map(lambda n: int(n), input().split(' ')))
	CITY = []
	for i in range(M):
		tmp = input().split(' ')
		CITY.append({'pref': int(tmp[0]), 'year': int(tmp[1]), 'no': i + 1})
	CITY.sort(key=lambda c: (c['pref'], c['year']))
	order = 0
	pref = ''
	for c in CITY:
		if pref != c['pref']:
			pref = c['pref']
			order = 1
		else:
			order += 1
		c['id'] = digit6(pref) + digit6(order)
	CITY.sort(key=lambda c: c['no'])
	for i in range(len(CITY)):
		print(CITY[i]['id'])
main()


(n, m) = map(int, input().split())
py = [tuple(map(int, input().split())) for _ in range(m)]
spy = sorted(py, key=lambda x: x[1])
ids = {}
maxy = [1] * (n + 1)
for (p, y) in spy:
	ids[p, y] = maxy[p]
	maxy[p] += 1
for (p, y) in py:
	print('{:0=6}{:0=6}'.format(p, ids[p, y]))


(n, m) = map(int, input().split())
pyi = [list(map(int, input().split())) + [i] for i in range(m)]
pyi.sort()
pnow = pyi[0][0]
cnt = 1
ans = [-1 for _ in range(m)]
for (p, y, i) in pyi:
	if pnow != p:
		cnt = 1
		pnow = p
	ans[i] = str(p).zfill(6) + str(cnt).zfill(6)
	cnt += 1
print('\n'.join(ans))


(n, m) = map(int, input().split())
P = []
Y = []
I = []
for i in range(m):
	(a, b) = map(int, input().split())
	P.append(a)
	Y.append(b)
	I.append(i)
Z = zip(P, Y, I)
Z = sorted(Z)
(P, Y, I) = zip(*Z)
N = []
c = P[0]
d = 1
for i in range(m):
	if c == P[i]:
		N.append('{0:06d}{1:06d}'.format(c, d))
		d += 1
	else:
		c = P[i]
		d = 1
		N.append('{0:06d}{1:06d}'.format(c, d))
		d += 1
Z = zip(I, N)
Z = sorted(Z)
(I, N) = zip(*Z)
for i in N:
	print(i)


(N, M) = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]
res = [''] * M
ctr = [0] * (N + 1)
for (i, (p, y)) in sorted(enumerate(X), key=lambda x: (x[1][0], x[1][1])):
	ctr[p] += 1
	res[i] = '{:0>6}{:0>6}'.format(p, ctr[p])
print(*res, sep='\n')


(N, M) = list(map(int, input().split()))
no = {}
ken = [[] for i in range(N)]
for i in range(M):
	(p, y) = list(map(int, input().split()))
	no[i] = str(p) + '_' + str(y)
	ken[p - 1].append(y)
ans = {}
for i in range(N):
	ken[i].sort()
	for j in range(len(ken[i])):
		ans[str(i + 1) + '_' + str(ken[i][j])] = str(i + 1).zfill(6) + str(j + 1).zfill(6)
for i in range(M):
	print(ans[no[i]])


from collections import defaultdict
(N, M) = list(map(int, input().split()))
PY = [list(map(int, input().split())) for _ in range(M)]
di = defaultdict(list)
for (i, py) in enumerate(PY):
	di[py[0]].append([py[1], i])
ans = ['' for _ in range(M)]
for (k, v) in list(di.items()):
	v.sort()
	for (j, yi) in enumerate(v):
		s = str(k).zfill(6)
		t = str(j + 1).zfill(6)
		ans[yi[1]] = s + t
print('\n'.join(ans))


import sys
(n, m) = list(map(int, input().split()))
ls = [[i] + list(map(int, input().split())) for i in range(m)]
ls.sort(key=lambda x: x[2])
d = dict(list(zip(list(range(1, n + 1)), [0 for i in range(n)])))
for i in range(m):
	ls[i].append(d[ls[i][1]] + 1)
	d[ls[i][1]] += 1
	ls[i].append(str(ls[i][1]).zfill(6) + str(ls[i][3]).zfill(6))
ls.sort(key=lambda x: x[0])
for l in ls:
	print(l[-1])


(n, m) = map(int, input().split())
l = [[] for i in range(m)]
for i in range(m):
	(a, b) = map(int, input().split())
	l[i] = [a, b, i]
l = list(sorted(l, key=lambda x: (x[0], x[1])))
ans = [[] for i in range(m)]
x = 0
y = 1
for i in range(m):
	if x != l[i][0]:
		x = l[i][0]
		y = 1
	else:
		y += 1
	a = str(x).zfill(6)
	b = str(y).zfill(6)
	ans[i] = [a + b, l[i][2]]
ans = list(sorted(ans, key=lambda x: x[1]))
for i in range(m):
	print(ans[i][0])


from bisect import bisect_left
(N, M) = map(int, input().split())
PY = [list(map(int, input().split())) for _ in range(M)]
t = [[] for _ in range(N)]
for (P, Y) in PY:
	t[P - 1].append(Y)
for i in range(N):
	t[i].sort()
for (P, Y) in PY:
	print('%06d%06d' % (P, bisect_left(t[P - 1], Y) + 1))


import bisect
(N, M) = map(int, input().split())
PY = [list(map(int, input().split())) for _ in range(M)]
L = [[] for _ in range(N)]
for (P, Y) in PY:
	bisect.insort_left(L[P - 1], Y)
for (P, Y) in PY:
	P_ans = str(P).zfill(6)
	Y_ans = str(bisect.bisect_right(L[P - 1], Y)).zfill(6)
	print(P_ans, Y_ans, sep='')


(N, M) = map(int, input().split())
prefec = [[] for _ in range(N)]
for i in range(M):
	(p, y) = map(int, input().split())
	prefec[p - 1].append((y, i))
ans = [None] * M
for (i, y) in enumerate(prefec):
	y.sort()
	for (k, (y, j)) in enumerate(y):
		ans[j] = '%06d%06d' % (i + 1, k + 1)
print(*ans, end='\n')


import bisect
(n, m) = map(int, input().split())
li = [[] for _ in range(n + 1)]
num = []
for _ in range(m):
	(p, y) = map(int, input().split())
	li[p].append(y)
	num.append((p, y))
for i in range(n + 1):
	li[i].sort()
for (i, j) in num:
	print(str(i).zfill(6) + str(bisect.bisect_left(li[i], j) + 1).zfill(6))


import math
from math import gcd, pi, sqrt
INF = float('inf')
import sys
sys.setrecursionlimit(10 ** 6)
import itertools
from collections import Counter, deque

def i_input():
	return int(input())

def i_map():
	return list(map(int, input().split()))

def i_list():
	return list(i_map())

def i_row(N):
	return [i_input() for _ in range(N)]

def i_row_list(N):
	return [i_list() for _ in range(N)]

def s_input():
	return input()

def s_map():
	return input().split()

def s_list():
	return list(s_map())

def s_row(N):
	return [s_input for _ in range(N)]

def s_row_str(N):
	return [s_list() for _ in range(N)]

def s_row_list(N):
	return [list(s_input()) for _ in range(N)]

def main():
	(n, m) = i_map()
	l = []
	for i in range(m):
		(p, y) = i_map()
		l.append([i, p, y, 0])
	l.sort(key=lambda x: (x[1], x[2]))
	ken = l[0][1]
	cnt = 1
	for i in l:
		if i[1] == ken:
			i[3] = cnt
			cnt += 1
		else:
			i[3] = 1
			cnt = 2
			ken = i[1]
	l.sort(key=lambda x: x[0])
	ans = []
	for i in l:
		ans.append(str(i[1]).zfill(6) + str(i[3]).zfill(6))
	for i in ans:
		print(i)

def __starting_point():
	main()
__starting_point()


(n, m) = map(int, input().split())
c = [[] for _ in range(n)]
for i in range(m):
	(p, y) = map(int, input().split())
	c[p - 1].append([i, y])
ans = [0] * m
for i in range(n):
	c[i].sort(key=lambda x: x[1])
	for j in range(len(c[i])):
		ID = str(i + 1).zfill(6) + str(j + 1).zfill(6)
		ans[c[i][j][0]] = ID
print(*ans, sep='\n')


I = lambda : map(int, input().split())
(n, m) = I()
l = [[] for _ in range(n + 1)]
for i in range(m):
	(p, y) = I()
	l[p].append([y, i])
a = []
for p in range(1, n + 1):
	l[p].sort()
	for (i, t) in enumerate(l[p]):
		a.append([t[1], '%06d' % p + '%06d' % -~i])
a.sort()
for t in a:
	print(t[1])


from bisect import bisect_left
(n, m) = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(m)]
t = [[] for _ in range(n)]
for (p, y) in data:
	t[p - 1].append(y)
for i in range(n):
	t[i].sort()
for (p, y) in data:
	nth = bisect_left(t[p - 1], y) + 1
	print('%06d%06d' % (p, nth))


import sys
f = lambda : map(int, sys.stdin.readline().split())
(_, m) = f()
(d, t, c) = ({}, 0, 0)
for (p, y, i) in sorted((list(f()) + [i] for i in range(m))):
	if p > t:
		(t, c) = (p, 1)
	else:
		c += 1
	d[i] = str(p).zfill(6) + str(c).zfill(6)
for (_, v) in sorted(d.items()):
	print(v)


(n, m) = (int(i) for i in input().split())
py = [[int(i) for i in input().split()] for i in range(m)]
cnt = [0] * (n + 1)
ids = {}
for (p, y) in sorted(py, key=lambda x: x[1]):
	cnt[p] += 1
	ids[y] = '%06d%06d' % (p, cnt[p])
for (_, y) in py:
	print(ids[y])


(N, M) = map(int, input().split())
py = [list(map(int, input().split())) for _ in range(M)]
cnt = [0] * (N + 1)
ids = {}
for (p, y) in sorted(py, key=lambda x: x[1]):
	cnt[p] += 1
	ids[y] = '%06d%06d' % (p, cnt[p])
for (_, y) in py:
	print(ids[y])


(N, M) = list(map(int, input().split()))
PY = [list(map(int, input().split())) + [i] for i in range(M)]
sortPY = sorted(PY, key=lambda x: x[1])
prefec = [0] * (N + 1)
res = []
for (p, y, i) in sortPY:
	prefec[p] += 1
	strp = str(p)
	ID = '0' * (6 - len(strp)) + strp + '0' * (6 - len(str(prefec[p]))) + str(prefec[p])
	res.append([ID, i])
sortres = sorted(res, key=lambda x: x[1])
for i in range(M):
	print(sortres[i][0])


(n, m) = map(int, input().split())
alist = []
for i in range(m):
	(p, y) = map(int, input().split())
	alist.append([i + 1, p, y])
alist.sort(key=lambda x: x[2])
blist = [0] * (n + 1)
ans = [0] * m
for i in range(m):
	blist[alist[i][1]] += 1
	ans1 = '0' * (6 - len(str(alist[i][1])))
	ans2 = str(alist[i][1])
	ans3 = '0' * (6 - len(str(blist[alist[i][1]])))
	ans4 = str(blist[alist[i][1]])
	ans[alist[i][0] - 1] = ans1 + ans2 + ans3 + ans4
for i in range(m):
	print(ans[i])


from collections import defaultdict
from bisect import bisect
(N, M, *P) = map(int, open(0).read().split())
d = defaultdict(list)
Z = set()
for (n, m) in zip(*[iter(P)] * 2):
	d[n].append(m)
	Z.add(n)
for z in Z:
	d[z].sort()
for (n, m) in zip(*[iter(P)] * 2):
	print(str(n).zfill(6) + str(bisect(d[n], m)).zfill(6))


(n, m) = list(map(int, input().split()))
cities = []
for i in range(m):
	(p, y) = list(map(int, input().split()))
	cities.append([p, y, i])
sorted_cities = sorted(cities, key=lambda x: (x[0], x[1]))
cnt = 1
ans = []
for i in range(m - 1):
	p_id = str(sorted_cities[i][0]).rjust(6, '0')
	c_id = str(cnt).rjust(6, '0')
	ans.append([sorted_cities[i][2], p_id + c_id])
	if sorted_cities[i][0] != sorted_cities[i + 1][0]:
		cnt = 1
	else:
		cnt += 1
p_id = str(sorted_cities[m - 1][0]).rjust(6, '0')
c_id = str(cnt).rjust(6, '0')
ans.append([sorted_cities[m - 1][2], p_id + c_id])
ans.sort()
for id in ans:
	print(id[1])


(n, m) = map(int, input().split())
li = []
for i in range(m):
	li.append(list(map(int, input().split())) + [i])
li.sort()
cac = li[0][0]
o = 2
li[0][1] = 1
for g in li[1:]:
	if g[0] != cac:
		cac = g[0]
		o = 1
	g[1] = o
	o += 1
li.sort(key=lambda x: x[-1])
for g in li:
	print('%06d' % g[0] + '%06d' % g[1])


(n, m) = map(int, input().split())
cities = [list(map(int, input().split())) + [i] for i in range(m)]
i = 0
pre_pref = 0
res = ['' for _ in range(m)]
for (idx, city) in enumerate(sorted(cities)):
	if pre_pref != city[0]:
		i = 0
		pre_pref = city[0]
	i += 1
	res[city[2]] = '{:06}{:06}'.format(city[0], i)
print('\n'.join(res))


from collections import defaultdict
import bisect
(N, M) = map(int, input().split())
P = [[int(i) for i in input().split()] for _ in range(M)]
D = defaultdict(list)
for (p, y) in sorted(P):
	D[p] += [y]
for (p, y) in P:
	z = bisect.bisect(D[p], y)
	print('%06d%06d' % (p, z))


(N, M) = map(int, input().split())
PY = [tuple(list(map(int, input().split())) + [i]) for i in range(M)]
PY.sort(key=lambda x: x[1])
ans = [''] * M
P = [0] * N
for (p, y, i) in PY:
	ret = ''
	p -= 1
	P[p] += 1
	ret += '{:0=6}'.format(p + 1)
	ret += '{:0=6}'.format(P[p])
	ans[i] = ret
print(*ans, sep='\n')


(n, m) = map(int, input().split())
p = []
for i in range(m):
	x = str(i) + ' ' + input()
	p.append(list(map(int, x.split())))
p.sort(key=lambda x: x[2])
c = [1] * (n + 1)
for i in range(m):
	p[i][2] = c[p[i][1]]
	c[p[i][1]] += 1
p.sort()
for i in range(m):
	print(str(p[i][1]).zfill(6) + str(p[i][2]).zfill(6))


(N, M) = map(int, input().split())
cnt = [0 for i in range(N + 1)]
A = []
for i in range(M):
	(P, val) = map(int, input().split())
	A.append((val, P, i))
A.sort()
B = []
for (val, P, i) in A:
	cnt[P] += 1
	B.append((i, '{:06}{:06}'.format(P, cnt[P])))
B.sort()
for (i, b) in B:
	print(b)


(n, m) = [int(i) for i in input().split()]
id = [[int(i) for i in input().split()] + [j] for j in range(m)]
pre_num = [0] * (n + 1)
ans = [''] * m
id.sort(key=lambda x: x[1])
for (p, y, i) in id:
	pre_num[p] += 1
	ans[i] = str(p).zfill(6) + str(pre_num[p]).zfill(6)
print('\n'.join(ans))


(n, m) = map(int, input().split())
d = [0] * m
K = [[] for i in range(n)]
for i in range(m):
	(p, y) = map(int, input().split())
	K[p - 1].append((i, y))
for i in range(n):
	K[i].sort(key=lambda x: x[1])
	c = 1
	for (a, b) in K[i]:
		ken = str(i + 1)
		t = str(c)
		d[a] = str('0' * (6 - len(ken))) + ken + str('0' * (6 - len(t))) + t
		c += 1
for i in d:
	print(i)


(N, M) = map(int, input().split())
A = [[] for i in range(N)]
for i in range(M):
	(a, b) = map(int, input().split())
	A[a - 1].append((b, i))
ans = [0] * M
for i in range(N):
	d = sorted(A[i])
	n = len(d)
	for j in range(n):
		(a, b) = d[j]
		D = str(i + 1)
		E = str(j + 1)
		r = D.zfill(6) + E.zfill(6)
		ans[b] = r
for i in ans:
	print(i)


import collections
import bisect
(N, M) = map(int, input().split())
P = [list(map(int, input().split())) for _ in range(M)]
a = collections.defaultdict(list)
for (x, y) in sorted(P):
	a[x] += [y]
for (x, y) in P:
	idx = bisect.bisect(a[x], y)
	print(str(x).zfill(6), str(idx).zfill(6), sep='')


(N, M) = map(int, input().split())
P = []
for i in range(M):
	(p, y) = map(int, input().split())
	P.append([y, p, i])
P.sort()
ken = [0] * N
shis = [''] * M
for (y, p, i) in P:
	ken[p - 1] += 1
	shis[i] = str(p).zfill(6) + str(ken[p - 1]).zfill(6)
for shi in shis:
	print(shi)


(n, m) = map(int, input().split())
p_cnt = [0 for i in range(n + 1)]
a = []
for i in range(m):
	(p, y) = map(int, input().split())
	a.append((y, p, i))
a.sort()
b = []
for (y, p, i) in a:
	p_cnt[p] += 1
	b.append((i, '{0:06}{1:06}'.format(p, p_cnt[p])))
b.sort()
for (i, bi) in b:
	print(bi)


(n, m) = list(map(int, input().split()))
ans = []
re = [[] for _ in range(n)]
for _ in range(m):
	a = list(map(int, input().split()))
	re[a[0] - 1].append(a[1])
	ans.append(a)
d = {}
for f in re:
	new = sorted(f)
	for i in range(len(new)):
		d[new[i]] = i + 1
for x in ans:
	p = x[0]
	q = d[x[1]]
	print(str('{:0=6}'.format(p)) + str('{:0=6}'.format(q)))


(n, m) = map(int, input().split())
a = [[] for _ in range(n)]
ans = [None] * m
for i in range(m):
	(p, y) = map(int, input().split())
	a[p - 1].append((y, i))
for (i, b) in enumerate(a):
	b.sort()
	for (j, (y, k)) in enumerate(b):
		ans[k] = '%06d%06d' % (i + 1, j + 1)
print(*ans, sep='\n')


(n, m) = map(int, input().split())
buf = [None] * m
cnt = {k: [] for k in range(n + 1)}
for i in range(m):
	(p, y) = map(int, input().split())
	cnt[p].append((y, i))
for (p, l) in cnt.items():
	if not l:
		continue
	l.sort()
	for (j, (y, i)) in enumerate(l):
		buf[i] = '{:06d}{:06d}'.format(p, j + 1)
print('\n'.join(buf))


(N, M) = map(int, input().split())
ypi = []
for i in range(M):
	(p, y) = map(int, input().split())
	ypi.append([y, p, i])
ypi.sort()
rank = [0] * N
ans = [''] * M
for count in range(M):
	(y, p, i) = ypi[count]
	rank[p - 1] += 1
	ans[i] = '{:06}'.format(p) + '{:06}'.format(rank[p - 1])
for s in ans:
	print(s)


((n, m), *q) = [[*list(map(int, i.split()))] for i in open(0)]
s = sorted(q)
d = {}
for (k, v) in s:
	if k not in d:
		d[k] = []
	d[k].append(v)
c = {}
for (k, v) in list(d.items()):
	i = 0
	if k not in c:
		c[k] = {}
	while i < len(v):
		i += 1
		c[k][v[~-i]] = str(i)
for (p, y) in q:
	pn = '00000' + str(p)
	cn = '00000' + c[p][y]
	print(pn[-6:] + cn[-6:])


import collections, bisect
(N, M) = map(int, input().split())
PY = [list(map(int, input().split())) for i in range(M)]
a = collections.defaultdict(list)
for (city, year) in sorted(PY):
	a[city] += [year]
for (city, year) in PY:
	z = bisect.bisect(a[city], year)
	print('%06d%06d' % (city, z))


import bisect
(N, M) = map(int, input().split())
q = [[int(j) for j in input().split()] for i in range(M)]
li = [[] for k in range(N + 1)]
for (i, j) in sorted(q):
	li[i].append(j)
for (p, y) in q:
	z = bisect.bisect(li[p], y)
	print('{:0=6}'.format(p) + '{:0=6}'.format(z))


(N, M) = list(map(int, input().split()))
PY = [list(map(int, input().split())) + [i] + [0] for i in range(M)]
PY_sorted = sorted(PY, key=lambda a: (a[0], a[1]))
PY_sorted[0][3] = str(PY_sorted[0][0]).zfill(6) + str(1).zfill(6)
cnt = 1
for i in range(1, M):
	cnt += 1
	if PY_sorted[i][0] != PY_sorted[i - 1][0]:
		cnt = 1
		PY_sorted[i][3] = str(PY_sorted[i][0]).zfill(6) + str(cnt).zfill(6)
	else:
		PY_sorted[i][3] = str(PY_sorted[i][0]).zfill(6) + str(cnt).zfill(6)
ans = sorted(PY_sorted, key=lambda a: a[2])
for a in ans:
	print(a[3])


(N, M) = map(int, input().split())
pref = [[0] for i in range(N + 1)]
q = []
for i in range(M):
	(p, y) = map(int, input().split())
	pref[p].append(y)
	q.append([p, y])
for p in pref:
	p.sort()
import bisect
for (p, y) in q:
	print('%06d%06d' % (p, bisect.bisect_left(pref[p], y)))


(N, M) = list(map(int, input().split()))
li = [0] * M
for i in range(M):
	(P, Y) = list(map(int, input().split()))
	li[i] = (P, Y)
li2 = sorted(li)
s = '000000'
tmp = 0
cnt = 1
dic = {}
for i in li2:
	if tmp == i[0]:
		cnt += 1
	else:
		cnt = 1
		tmp = i[0]
	s1 = s[0:6 - len(str(i[0]))] + str(i[0])
	s2 = s[0:6 - len(str(cnt))] + str(cnt)
	s3 = s1 + s2
	dic[i] = s3
for i in li:
	print(dic[i])


import math
(n, m) = map(int, input().split(' '))
pyL = sorted([[i] + list(map(int, input().split(' '))) for i in range(m)], key=lambda x: x[2])
li = [1] * (n + 1)
for i in range(len(pyL)):
	(index, p, y) = pyL[i]
	pyL[i].append(str(p).zfill(6) + str(li[p]).zfill(6))
	li[p] += 1
for py in sorted(pyL, key=lambda x: x[0]):
	print(py[3])


r = lambda i: ('0' * 6 + str(i))[-6:]
I = lambda : map(int, input().split())
(N, M) = I()
C = [[i] + list(I()) for i in range(M)]
C = sorted(C, key=lambda x: (x[1], x[2]))
q = 1
c = 1
l = []
for (i, p, _) in C:
	(q, c) = (p, 1) if p > q else (q, c)
	l += [[i, r(p) + r(c)]]
	c += 1
for (_, s) in sorted(l, key=lambda x: x[0]):
	print(s)


(N, M) = map(int, input().split())
PY = [list(map(int, input().split())) + [i] for i in range(M)]
PY.sort(key=lambda x: [x[0], x[1]])
ans = []
P = [0] * (N + 1)
for (p, y, i) in PY:
	P[p] += 1
	tmp = str(p).zfill(6) + str(P[p]).zfill(6)
	ans.append([i, tmp])
ans.sort()
for (i, a) in ans:
	print(a)


(n, m) = map(int, input().split())
Y = [0] * m
P = [0] * m
for i in range(m):
	(P[i], Y[i]) = map(int, input().split())
yp = list(zip(Y, P, range(m)))
yp.sort()
underdigit = [0] * (n + 1)
ans = [''] * m
for (y, p, i) in yp:
	underdigit[p] += 1
	ans[i] = '%06d%06d' % (p, underdigit[p])
for a in ans:
	print(a)


from bisect import bisect_left
from collections import defaultdict
(n, m) = map(int, input().split())
m = [tuple(map(int, input().split())) for _ in range(m)]
d = defaultdict(list)
for (p, y) in sorted(m):
	d[p].append(y)
for (p, y) in m:
	print('{:06}{:06}'.format(p, bisect_left(d[p], y) + 1))


(n, m) = list(map(int, input().split()))
py = []
for i in range(m):
	(_p, _y) = list(map(int, input().split()))
	py.append([_p, _y, i])
py = sorted(py, key=lambda x: (x[0], x[1]))
ans = []
p = -1
x = 1
for i in range(m):
	if p != py[i][0]:
		x = 1
		p = py[i][0]
	else:
		x += 1
	pid = str(py[i][0]).zfill(6)
	xid = str(x).zfill(6)
	ans.append([pid + xid, py[i][2]])
ans = sorted(ans, key=lambda x: x[1])
for (a, i) in ans:
	print(a)


(n, m) = map(int, input().split())
py = []
mli = [0] * n
li = [''] * m
for i in range(m):
	(p, y) = map(int, input().split())
	py.append([p, y, i])
py.sort(key=lambda x: x[1])
for (p, y, i) in py:
	mli[p - 1] += 1
	pi = str(p).zfill(6)
	yi = str(mli[p - 1]).zfill(6)
	li[i] = pi + yi
for i in li:
	print(i)


(n, m) = map(int, input().split())
c = [list(map(int, input().split())) + [i] for i in range(m)]
d = c[:]
d.sort(key=lambda val: val[1])
k = [0] * 100010
ans = []
for i in d:
	ans.append([i[2], i[0], k[i[0]] + 1])
	k[i[0]] += 1
ans.sort()
for i in ans:
	print(str(i[1]).zfill(6) + str(i[2]).zfill(6))


(n, m) = map(int, input().split())
lst = [[] for _ in range(n)]
for i in range(m):
	(p, y) = map(int, input().split())
	lst[p - 1].append((y, i))
ans = [None] * m
for (i, d) in enumerate(lst):
	d.sort()
	for (j, (Y, I)) in enumerate(d):
		ans[I] = str(i + 1).zfill(6) + str(j + 1).zfill(6)
for i in ans:
	print(i)


(n, m) = map(int, input().split())
py = [list(map(int, input().split())) + [i] for i in range(m)]
py.sort(key=lambda x: x[1])
ans = []
cnt = [0] * n
for (p, y, i) in py:
	ans.append(['{0:06d}{1:06d}'.format(p, cnt[p - 1] + 1), i])
	cnt[p - 1] += 1
ans.sort(key=lambda x: x[1])
for (a, i) in ans:
	print(a)


class Info:

	def __init__(self, num, p, y, id):
		self.num = num
		self.p = p
		self.y = y
		self.id = id
(n, m) = map(int, input().split())
info = [Info(0, 0, 0, '')]
for num in range(1, m + 1):
	(p, y) = map(int, input().split())
	info.append(Info(num, p, y, ''))
info = sorted(info, key=lambda x: (x.p, x.y))
cnt = 1
for i in range(1, m + 1):
	if info[i].p != info[i - 1].p:
		cnt = 1
	else:
		cnt += 1
	info[i].id = '{0:06d}{1:06d}'.format(info[i].p, cnt)
info = sorted(info, key=lambda x: x.num)
info.pop(0)
for x in info:
	print(x.id)


(N, M) = list(map(int, input().split()))
PY = []
for i in range(M):
	PY.append([i] + list(map(int, input().split())))
PY.sort(key=lambda x: x[2])
ans = []
C = [0] * (N + 1)
for (i, P, Y) in PY:
	C[P] += 1
	ans.append([i, '{:0=6}{:0=6}'.format(P, C[P])])
ans.sort()
for (i, a) in ans:
	print(a)


(N, M) = map(int, input().split())
d = {}
PY = []
import bisect
for _ in range(M):
	(p, y) = map(int, input().split())
	PY.append((p, y))
	t = d.get(p, [0])
	i = bisect.bisect_left(t, y)
	t.insert(i, y)
	d[p] = t
dx = {}
for (k, v) in d.items():
	for i in range(len(v)):
		dx[k, v[i]] = i
for (p, y) in PY:
	print(str(p).zfill(6) + str(dx[p, y]).zfill(6))


(n, m) = map(int, input().split())
a = []
for i in range(m):
	(x, y) = map(int, input().split())
	a.append([x, y])
b = a.copy()
c = sorted(b, key=lambda x: (x[0], x[1]))
d = [{} for i in range(10 ** 5 + 1)]
count = 1
s = '%d' % c[0][0]
s = s.zfill(6)
s2 = '%d' % count
s2 = s2.zfill(6)
d1 = {c[0][1]: s + s2}
for i in range(1, m):
	if c[i][0] == c[i - 1][0]:
		count += 1
		s2 = '%d' % count
		s2 = s2.zfill(6)
		d1[c[i][1]] = s + s2
	else:
		d[c[i - 1][0]] = d1
		count = 1
		s = '%d' % c[i][0]
		s = s.zfill(6)
		s2 = '%d' % count
		s2 = s2.zfill(6)
		d1 = {c[i][1]: s + s2}
d[c[-1][0]] = d1
for i in range(m):
	d2 = d[a[i][0]]
	print(d2.get(a[i][1]))


(n, m) = map(int, input().split())
s = [[] for _ in range(n + 1)]
for i in range(m):
	(p, y) = map(int, input().split())
	s[p].append([y, i])
ans = [0] * m
for p in range(1, n + 1):
	cnt = 1
	for (y, i) in sorted(s[p]):
		ans[i] = '{:06}{:06}'.format(p, cnt)
		cnt += 1
for j in range(len(ans)):
	print(ans[j])


(N, M) = map(int, input().split())
A = []
for i in range(M):
	(P, Y) = map(int, input().split())
	A.append([P, Y, i])
ans = [''] * M
A = sorted(A, key=lambda x: x[1])
A = sorted(A, key=lambda x: x[0])
now = A[0][0]
cnt = 1
for i in range(M):
	pref = str(A[i][0])
	if A[i][0] != now:
		cnt = 1
	year = str(cnt)
	now = A[i][0]
	cnt += 1
	ans[A[i][2]] = pref.zfill(6) + year.zfill(6)
for i in range(M):
	print(ans[i])


from operator import itemgetter
(n, m) = map(int, input().split())
yp = []
for i in range(m):
	(p_, y_) = map(int, input().split())
	yp.append([y_, p_, i + 1])
py = sorted(yp)
ken = [0] * n
res = []
for i in range(m):
	ken[py[i][1] - 1] += 1
	(p, q, r) = (py[i][1], ken[py[i][1] - 1], py[i][2])
	res.append([p, q, r])
res.sort(key=itemgetter(2))
for i in range(m):
	ans1 = [0] * (6 - len(str(res[i][0])))
	ans1.append(res[i][0])
	ans2 = [0] * (6 - len(str(res[i][1])))
	ans2.append(res[i][1])
	print(*ans1, *ans2, sep='')


(N, M) = map(int, input().split())
D = []
for i in range(M):
	(P, Y) = map(int, input().split())
	D.append((i, P, Y))
D.sort(key=lambda x: x[2])
X = [1 for _ in range(N + 1)]
A = []
for (i, p, y) in D:
	A.append((i, '{0:06d}{1:06d}'.format(p, X[p])))
	X[p] += 1
A.sort()
for (i, x) in A:
	print(x)


from bisect import bisect_left
(n, m) = map(int, input().split())
py = []
l = [[] for _ in range(n + 1)]
for _ in range(m):
	(p, y) = map(int, input().split())
	l[p].append(y)
	py.append((p, y))
for i in l:
	i.sort()
for (p, y) in py:
	s = str(p)
	t = str(bisect_left(l[p], y) + 1)
	ans = '0' * (6 - len(s)) + s + '0' * (6 - len(t)) + t
	print(ans)


(n, m) = list(map(int, input().split()))
pre = [[] for i in range(n)]
pre_num = [[] for i in range(n)]
city = []
for i in range(m):
	(p, y) = list(map(int, input().split()))
	pre[p - 1].append(y)
	city.append(p - 1)
from bisect import bisect_right
for i in range(n):
	town = sorted(pre[i])
	for j in range(len(town)):
		pre_num[i].append(bisect_right(town, pre[i][j]))
cnt = [0 for i in range(n)]
for i in city:
	print(str(i + 1).zfill(6) + str(pre_num[i][cnt[i]]).zfill(6))
	cnt[i] += 1


(n, m) = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]
c = [0] * -~n
id = {}
for (p, y) in sorted(a, key=lambda x: x[1]):
	c[p] += 1
	id[y] = str(p).zfill(6) + str(c[p]).zfill(6)
for (_, y) in a:
	print(id[y])


from bisect import bisect_right
(n, m) = map(int, input().split())
(p, y) = ([], [])
l = {}
for i in range(m):
	(p_, y_) = map(int, input().split())
	p.append(p_)
	y.append(y_)
	if not p_ in l:
		l[p_] = []
	l[p_].append(y_)
for i in l:
	l[i].sort()
for i in range(m):
	print(str(p[i]).zfill(6) + str(bisect_right(l[p[i]], y[i])).zfill(6))


f = lambda : map(int, input().split())
(n, m) = f()
ll = [list(f()) for _ in range(m)]
l = [0] * n
d = {}
for (p, y) in sorted(ll, key=lambda k: k[1]):
	l[p - 1] += 1
	d[y] = str(p).zfill(6) + str(l[p - 1]).zfill(6)
for l in ll:
	print(d[l[1]])


(n, m) = map(int, input().split())
dic = {}
ans = [0] * m
for i in range(m):
	(p, y) = map(int, input().split())
	dic.setdefault(p, []).append([y, i])
for (i, j) in dic.items():
	j = sorted(j)
	for (k, l) in enumerate(j):
		ans[l[1]] = str(i).zfill(6) + str(k + 1).zfill(6)
for i in range(len(ans)):
	print(ans[i])


(n, m) = list(map(int, input().split(' ')))
py = []
for i in range(m):
	py.append(list(map(int, input().split(' '))) + [i])
py.sort()
ids = []
c = 1
p = 1
for j in py:
	if j[0] != p:
		c = 1
		p = j[0]
	ids.append([j[2], '{:0>6}{:0>6}'.format(j[0], c)])
	c += 1
ids.sort()
for i in ids:
	print(i[1])


import bisect
(n, m) = map(int, input().split())
Q = []
P = [[] for _ in range(n)]
for i in range(m):
	(p, y) = map(int, input().split())
	Q.append([p, y])
	P[p - 1].append(y)
P_1 = [sorted(l) for l in P]
for (p, y) in Q:
	a = str(p).zfill(6)
	b = str(bisect.bisect(P_1[p - 1], y)).zfill(6)
	print(a + b)


from collections import defaultdict as dd
d = dd(int)
(n, m) = map(int, input().split())
l = [[i] + list(map(int, input().split())) + [0] for i in range(m)]
o = sorted(l, key=lambda x: x[2])
for (i, j) in enumerate(o):
	d[j[1]] += 1
	o[i][3] = d[j[1]]
for i in sorted(o):
	print('%06d%06d' % (i[1], i[3]))


(n, m) = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]
b = [[] for _ in range(n + 1)]
for i in range(m):
	b[a[i][0]].append((a[i][1], i + 1))
for i in range(1, n + 1):
	b[i].sort()
ans = ['.'] * m
for i in range(1, n + 1):
	for j in range(len(b[i])):
		ans[b[i][j][1] - 1] = '0' * (6 - len(str(i))) + str(i) + '0' * (6 - len(str(j + 1))) + str(j + 1)
print(*ans, sep='\n')


(N, M) = map(int, input().split())
A = [[] for i in range(N)]
for i in range(M):
	(p, y) = map(int, input().split())
	A[p - 1].append((y, i))
X = [0] * M
for (i, d) in enumerate(A):
	d.sort()
	for (k, (y, j)) in enumerate(d):
		X[j] = str(i + 1).zfill(6) + str(k + 1).zfill(6)
print(*X, sep='\n')


(N, M) = map(int, input().split())
PY = [tuple(map(int, input().split())) for i in range(M)]
PY_sort = sorted(PY)
tmp = dict()
before = 0
for py in PY_sort:
	if before != py[0]:
		before = py[0]
		count = 0
	count += 1
	tmp[py] = count
for py in PY:
	print('{:06}{:06}'.format(py[0], tmp[py]))


(N, M) = map(int, input().split())
PY = [list(map(int, input().split())) + [0] for _ in range(M)]
sort_PY = sorted(PY, key=lambda x: x[1])
d = {}
for py in sort_PY:
	if py[0] not in d:
		d[py[0]] = 1
	else:
		d[py[0]] += 1
	py[2] = d[py[0]]
for py in PY:
	print(str(py[0]).zfill(6) + str(py[2]).zfill(6))


(N, M) = map(int, input().split())
C = [tuple(map(int, input().split())) for _ in range(M)]
P = {c[0]: [] for c in C}
for c in C:
	P[c[0]].append(c[1])
for p in P:
	P[p].sort()
	P[p] = {P[p][i]: i + 1 for i in range(len(P[p]))}
for c in C:
	print('{:06}{:06}'.format(c[0], P[c[0]][c[1]]))


import bisect
import collections
(N, M) = map(int, input().split())
PM = [[int(j) for j in input().split()] for i in range(M)]
A = collections.defaultdict(list)
for (x, y) in sorted(PM):
	A[x] += [y]
for (x, y) in PM:
	z = bisect.bisect(A[x], y)
	print('%06d%06d' % (x, z))


(N, M) = map(int, input().split())
PY = [list(map(int, input().split())) for i in range(M)]
PYI = sorted([(p, y, i) for (i, (p, y)) in enumerate(PY)])
r = [''] * M
(a, b) = (0, 0)
for (p, y, i) in PYI:
	if a != p:
		(a, b) = (p, 1)
	else:
		b += 1
	r[i] = str(p).zfill(6) + str(b).zfill(6)
print(*r, sep='\n')


(N, M) = map(int, input().split())
pys = []
for i in range(M):
	(p, y) = map(int, input().split())
	pys.append([p, y, i])
nums = [0] * N
ans = [''] * M
pys.sort(key=lambda x: x[1])
for (p, y, i) in pys:
	nums[p - 1] += 1
	ans[i] = str(p).zfill(6) + str(nums[p - 1]).zfill(6)
for an in ans:
	print(an)


(N, M) = map(int, input().split())
PY = [tuple(map(int, input().split())) for i in range(M)]
py_map = {}
x = 1
prep = 0
for (p, y) in sorted(PY):
	if prep == p:
		x += 1
	else:
		x = 1
	py_map[p, y] = str(p).zfill(6) + str(x).zfill(6)
	prep = p
for (p, y) in PY:
	print(py_map[p, y])


def make_code(prifacture_num, city_num):
	s1 = str(prifacture_num)
	while len(s1) != 6:
		s1 = '0' + s1
	s2 = str(city_num)
	while len(s2) != 6:
		s2 = '0' + s2
	return s1 + s2
(prifacture_cnt, city_cnt) = list(map(int, input().split()))
data = [list(map(int, input().split())) for i in range(city_cnt)]
city_data = []
for i in range(city_cnt):
	city_data.append([data[i][0], data[i][1], i])
city_data.sort()
city_code = []
prifacture = city_data[0][0]
cnt = 0
for city in city_data:
	if prifacture == city[0]:
		cnt += 1
		s = make_code(prifacture, cnt)
		city_code.append([city[2], s])
	else:
		cnt = 1
		prifacture = city[0]
		s = make_code(prifacture, cnt)
		city_code.append([city[2], s])
city_code.sort()
for (num, code) in city_code:
	print(code)


(n, m) = map(int, input().split())
l = [[] for _ in range(n)]
for i in range(m):
	(p, y) = map(int, input().split())
	l[p - 1].append((y, i))
ans = [None] * m
for (i, pre) in enumerate(l):
	pre.sort()
	for (j, (a, b)) in enumerate(pre):
		ans[b] = '{:0>6}{:0>6}'.format(i + 1, j + 1)
print('\n'.join(ans))


from collections import defaultdict
import bisect
(n, m) = map(int, input().split())
a = [list(map(int, input().split())) for i in range(m)]
d = defaultdict(list)
for i in sorted(a):
	d[i[0]].append(i[1])
for (x, y) in a:
	print(str(x).zfill(6) + str(bisect.bisect_left(d[x], y) + 1).zfill(6))


(N, M) = map(int, input().split())
PY = [tuple([int(x) for x in input().split()]) for _ in range(M)]
d = dict()
cp = 0
n = 1
for (p, y) in sorted(PY):
	if p != cp:
		cp = p
		n = 1
	d[p, y] = n
	n += 1
for (p, y) in PY:
	print('%06d%06d' % (p, d[p, y]))


(N, M) = map(int, input().split())
ls = [[] for _ in range(N)]
for i in range(M):
	(p, y) = map(int, input().split())
	ls[p - 1].append((y, i))
ids = [None] * M
for i in range(N):
	ls[i].sort()
	for j in range(len(ls[i])):
		(y, k) = ls[i][j]
		ids[k] = '{:0>6}{:0>6}'.format(i + 1, j + 1)
print(*ids, sep='\n')


def solve(N, M, PY):
	ken = [0] * (N + 1)
	PY = [PY[i] + [i] for i in range(M)]
	PY.sort(key=lambda x: x[1])
	for i in range(M):
		(p, y, s) = PY[i]
		ken[p] += 1
		PY[i].append(ken[p])
	PY.sort(key=lambda x: x[2])
	for (p, y, s, n) in PY:
		print(('000000' + str(p))[-6:] + ('000000' + str(n))[-6:])

def __starting_point():
	(N, M) = list(map(int, input().split()))
	PY = [[int(i) for i in input().split()] for _ in range(M)]
	solve(N, M, PY)
__starting_point()


(N, M) = [int(x) for x in input().split()]
C = [0 for _ in range(N)]
V = []
IDs = []
for i in range(M):
	(P, Y) = [int(x) for x in input().split()]
	V.append([Y, P, i])
V.sort()
for v in V:
	C[v[1] - 1] += 1
	x = C[v[1] - 1]
	IDs.append(f'{v[2]:06d}{v[1]:06d}{x:06d}')
IDs.sort()
for i in IDs:
	print(i[6:])


(N, M) = list(map(int, input().split()))
C = []
for i in range(M):
	(p, y) = list(map(int, input().split()))
	C.append([i, p, y])
C.sort(key=lambda x: (x[1], x[2]))
ans = []
k = C[0][1]
n = 1
for i in range(M):
	city = C[i][1]
	if k != city:
		k = city
		n = 1
	number = f'{city:06}{n:06}'
	ans.append([C[i][0], number])
	n += 1
ans.sort(key=lambda x: x[0])
for i in range(M):
	print(ans[i][1])


import bisect
(n, m) = (int(i) for i in input().split())
a = [[] for _ in range(n)]
s = []
for _ in range(m):
	(x, c) = (int(i) for i in input().split())
	a[x - 1].append(c)
	s.append((x, c))
[a[i].sort() for i in range(n)]
for (x, c) in s:
	print('{:06}{:06}'.format(x, bisect.bisect_left(a[x - 1], c) + 1))


(n, m) = [int(i) for i in input().split()]
py = [[int(i) for i in input().split()] + [_, ''] for _ in range(m)]
kazu = [0] * (n + 1)
py.sort(key=lambda x: x[1])
for i in range(m):
	kazu[py[i][0]] += 1
	py[i][3] += str(kazu[py[i][0]])
py.sort(key=lambda x: x[2])
for i in range(m):
	print(str(py[i][0]).zfill(6) + py[i][3].zfill(6))


(N, M) = map(int, input().split())
d = [[] for _ in range(N + 1)]
for i in range(M):
	(P, Y) = map(int, input().split())
	d[P].append((Y, i))
dd = [''] * M
for P in range(1, N + 1):
	j = 1
	for (Y, i) in sorted(d[P]):
		dd[i] = '{:06}{:06}'.format(P, j)
		j += 1
print(*dd, sep='\n')


from collections import defaultdict
(n, m) = list(map(int, input().split()))
prefecture = [[] for _ in range(n + 1)]
tpl_lst = []
for i in range(m):
	(p, y) = list(map(int, input().split()))
	prefecture[p].append(y)
	tpl_lst.append((p, y))
for p in prefecture:
	if len(p) >= 2:
		p.sort()
d = defaultdict(list)
for (idx, pre) in enumerate(prefecture):
	if len(pre) >= 1:
		for (i, year) in enumerate(pre):
			d[idx, year] = [idx, i + 1]
for tpl in tpl_lst:
	id = d[tpl][0] * 10 ** 6 + d[tpl][1]
	id = str(id)
	id = '0' * (12 - len(id)) + id
	print(id)


import collections as coll
import bisect
(n, m) = map(int, input().split())
py = [list(map(int, input().split())) for _ in range(m)]
a = coll.defaultdict(list)
for (x, y) in sorted(py):
	a[x].append(y)
for (x, y) in py:
	z = bisect.bisect(a[x], y)
	print('%06d%06d' % (x, z))


(N, M) = map(int, input().split())
PY = [list(map(int, input().split())) + [0] for _ in range(M)]
sort_PY = sorted(PY, key=lambda x: x[1])
c = {}
for i in range(M):
	p = sort_PY[i][0]
	if p in c:
		c[p] += 1
	else:
		c[p] = 1
	sort_PY[i][2] = c[p]
for (p, y, z) in PY:
	print(str(p).zfill(6) + str(z).zfill(6))


(N, M) = list(map(int, input().split()))
import sys
l = [list(map(int, _.rstrip().split())) for _ in sys.stdin.readlines()]
n = sorted(l, key=lambda x: x[1])
dic = {}
mem = [0] * N
for (i, j) in n:
	mem[i - 1] += 1
	dic[i, j] = str(i).zfill(6) + str(mem[i - 1]).zfill(6)
for (i, j) in l:
	print(dic[i, j])


from collections import defaultdict
(N, M) = list(map(int, input().split()))
L = []
A = []
for _ in range(M):
	(p, y) = list(map(int, input().split()))
	L.append([p, y])
	A.append([p, y])
L.sort(key=lambda x: x[1])
ans_d = defaultdict()
dp = [0] * (N + 1)
for (i, v) in enumerate(L):
	s = ''
	if dp[v[0]] != 0:
		l_dp = 6 - len(str(dp[v[0]] + 1))
		for j in range(l_dp):
			s += '0'
		s += str(dp[v[0]] + 1)
		dp[v[0]] += 1
	else:
		l_dp = 6 - len(str(dp[v[0]] + 1))
		for j in range(l_dp):
			s += '0'
		s += str(dp[v[0]] + 1)
		dp[v[0]] += 1
	k = str(v[0]) + ' ' + str(v[1])
	ans_d[k] = s
for i in A:
	m = str(i[0]) + ' ' + str(i[1])
	k = 6 - len(str(i[0]))
	s = ''
	for j in range(k):
		s += '0'
	s += str(i[0])
	print(s + ans_d[m])


(n, m) = list(map(int, input().split()))
PY = [list(map(int, input().split())) + [0] for i in range(m)]
d = {}
for i in sorted(PY, key=lambda x: x[1]):
	if i[0] in d:
		d[i[0]] += 1
	else:
		d[i[0]] = 1
	i[2] = d[i[0]]
for i in PY:
	print(str(i[0]).zfill(6) + str(i[2]).zfill(6))


(N, M) = map(int, input().split())
P_Y = {i: list(map(int, input().split())) for i in range(M)}
P_city = [0] * N
P_res = [None] * M
for (i, (p, y)) in sorted(P_Y.items(), key=lambda x: x[1][1]):
	P_city[p - 1] += 1
	P_res[i] = (p, P_city[p - 1])
for (p, y) in P_res:
	print('{0:06d}{1:06d}'.format(p, y))


(N, M) = list(map(int, input().split()))
D = [[] for _ in range(N)]
for i in range(M):
	(p, y) = list(map(int, input().split()))
	D[p - 1].append((y, i))
ans = [0] * M
for (i, d) in enumerate(D):
	d.sort()
	for (k, (y, j)) in enumerate(d):
		ans[j] = str(i + 1).zfill(6) + str(k + 1).zfill(6)
print('\n'.join(ans))


(n, m) = list(map(int, input().split()))
ken = [1 for i in range(n + 1)]
inf = [[] for i in range(m)]

def f(x):
	m = 0
	while x > 0:
		m += 1
		x = x // 10
	return m
for i in range(m):
	(p, y) = list(map(int, input().split()))
	inf[i].append(i + 1)
	inf[i].append(p)
	inf[i].append(y)
inf = sorted(inf, key=lambda x: x[2])
for i in range(m):
	inf[i].append(ken[inf[i][1]])
	ken[inf[i][1]] += 1
inf = sorted(inf)
for i in range(m):
	ans = ''
	p = inf[i][1]
	y = inf[i][3]
	for j in range(6 - f(p)):
		ans += '0'
	ans = ans + str(p)
	for j in range(6 - f(y)):
		ans = ans + '0'
	ans = ans + str(y)
	print(ans)


(n, m) = map(int, input().split())
PY = [list(map(int, input().split())) + [_] for _ in range(m)]
from operator import itemgetter
I = [0] * (n + 1)
Ans = [''] * m
PY.sort(key=itemgetter(1))
for py in PY:
	I[py[0]] += 1
	Ans[py[2]] = str(format(py[0], '06d')) + str(format(I[py[0]], '06d'))
print(*Ans, sep='\n')


(n, m) = map(int, input().split())
py = []
for i in range(m):
	(p, y) = map(int, input().split())
	py.append([i, p, y])
cnt = [0] * (n + 1)
sorted_py = sorted(py, key=lambda x: (x[1], x[2]))
for i in range(m):
	cnt[sorted_py[i][1]] += 1
	city_id = str(sorted_py[i][1]).zfill(6) + str(cnt[sorted_py[i][1]]).zfill(6)
	sorted_py[i].append(city_id)
sorted_py = sorted(sorted_py, key=lambda x: x[0])
for i in range(m):
	print(sorted_py[i][3])


import bisect
(n, m) = list(map(int, input().split()))
ans = []
re = [[] for _ in range(n)]
for _ in range(m):
	a = list(map(int, input().split()))
	re[a[0] - 1].append(a[1])
	ans.append(a)
d = []
for f in re:
	sor = []
	new = sorted(list(set(f)))
	for i in f:
		c = bisect.bisect_left(new, i)
		sor.append(c + 1)
	d.append(sor)
for x in ans:
	p = x[0]
	q = d[p - 1].pop(0)
	print(str('{:0=6}'.format(p)) + str('{:0=6}'.format(q)))


(N, M) = map(int, input().split())
piys = [[] for _ in range(N)]
for i in range(M):
	(p, y) = map(int, input().split())
	piys[p - 1].append((y, i))
ans = [None] * M
for (p, iys) in enumerate(piys):
	iys.sort()
	for (k, (y, i)) in enumerate(iys):
		ans[i] = '%06d%06d' % (p + 1, k + 1)
for i in ans:
	print(i)


(N, M) = list(map(int, input().split()))
numbers = [{} for n in range(N)]
for m in range(M):
	(P, Y) = list(map(int, input().split()))
	numbers[P - 1][m] = Y
answers = {}
for n in range(N):
	number = numbers[n]
	if len(number) == 0:
		continue
	new_number = sorted(list(number.items()), key=lambda x: x[1])
	suuji = 1
	for num in new_number:
		answers[num[0]] = (6 - len(str(n + 1))) * '0' + str(n + 1) + (6 - len(str(suuji))) * '0' + str(suuji)
		suuji += 1
answer = sorted(list(answers.items()), key=lambda x: x[0])
for ans in answer:
	print(ans[1])


(n, m) = map(int, input().split())
py = [[0, 0, 0]] * m
for i in range(m):
	py[i] = list(map(int, input().split())) + [i]
ans = [''] * m
a = sorted(py)
j = 0
for i in range(len(a)):
	if i > 0 and a[i - 1][0] < a[i][0]:
		j = 1
	else:
		j += 1
	ans[a[i][2]] = '{:06}'.format(a[i][0]) + '{:06}'.format(j)
for i in range(m):
	print(ans[i])


(N, M) = map(int, input().split())
D = [[] for _ in range(N)]
for i in range(M):
	(P, Y) = map(int, input().split())
	D[P - 1].append((Y, i))
ans = [None] * M
for (i, d) in enumerate(D):
	d.sort()
	for (k, (Y, j)) in enumerate(d):
		ans[j] = '%06d%06d' % (i + 1, k + 1)
print(*ans, sep='\n')


import sys
from collections import deque
stdin = sys.stdin

def ns():
	return stdin.readline().rstrip()

def ni():
	return int(stdin.readline().rstrip())

def nm():
	return list(map(int, stdin.readline().split()))

def nl():
	return list(map(int, stdin.readline().split()))

def main():
	(n, m) = nm()
	Y = [deque() for _ in range(n)]
	Y_id = []
	order = []
	for i in range(m):
		(p, y) = nm()
		Y[p - 1].append(y)
		order.append(p)
	for y in Y:
		d = {}
		for (i, y_s) in enumerate(sorted(y)):
			d[y_s] = i + 1
		Y_id += [d]
	for o in order:
		print('{:06}'.format(o) + '{:06}'.format(Y_id[o - 1][Y[o - 1].popleft()]))

def __starting_point():
	main()
__starting_point()


(N, M) = map(int, input().split())
PY = [list(map(int, input().split())) + [i] for i in range(M)]
count = [0] * N
ans = [''] * M
PY.sort(key=lambda x: x[1])
for (p, _, i) in PY:
	count[p - 1] += 1
	ans[i] = str(p).zfill(6) + str(count[p - 1]).zfill(6)
for a in ans:
	print(a)


(n, m) = list(map(int, input().split()))
p_y = []
for i in range(m):
	(p, y) = list(map(int, input().split()))
	p_y.append([p, y, i])
p_y.sort()
res = [0] * m
order = 0
for i in range(m):
	(ken, _, index) = p_y[i]
	if ken != p_y[i - 1][0] and i > 0:
		order = 1
	else:
		order += 1
	res[index] = [ken, order]
for i in range(m):
	ken = str(res[i][0]).zfill(6)
	order = str(res[i][1]).zfill(6)
	print(ken + order)