Problem:
 Score: 300 points    Problem Statement 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 1 2 3
1 32
2 63
1 12      Sample Output 1 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 .        Sample Input 2 2 3
2 55
2 77
2 99      Sample Output 2 000002000001
000002000002
000002000003

Solution (Python):
import numpy as np

def main():
	buf = input().split()
	n = int(buf[0])
	m = int(buf[1])
	
	py = np.zeros((m, 4), dtype="int")
	for i in range(m):
		py[i][0] = i+1
		buf = input().split()
		py[i][1] = int(buf[0])
		py[i][2] = int(buf[1])
		
	py = np.array(sorted(py, key=lambda x:(x[1],x[2])))
	bufp = 0
	for i in range(m):
		if(py[i][1] != bufp):
			bufp = py[i][1]
			py[i][3] = 1
		else:
			py[i][3] = py[i-1][3]+1
	
	py = py[np.argsort(py[:, 0])]
	

	for i in range(m):
		ans = "{0:06d}".format(py[i][1])+"{0:06d}".format(py[i][3])
		print(ans)
	
main()

Solution (Python):
n, m = [int(x) for x in input().split()]
l = []
for i in range(m):
    tmp = [int(x) for x in input().split()]
    l.append([i, tmp[0], tmp[1]])
l.sort(key=lambda x: x[2])

prefecture = [0 for _ in range(n)]
city = [[] for _ in range(m)]

for info in l:
    i, p, y = info
    tmp = [p, prefecture[p-1]+1]
    prefecture[p-1] += 1
    city[i] = tmp

for x in city:
    p_str = str(x[0])
    c_str = str(x[1])
    p_add = '0'*(6 - len(p_str))
    c_add = '0' * (6 - len(c_str))
    p_str = p_add + p_str
    c_str = c_add + c_str
    print(p_str + c_str)

Solution (Python):
if __name__ == '__main__':
    _, m = map(int, input().split())
    pres = [[i] + [int(s) for s in input().split()] for i in range(m)]
    pres.sort(key=lambda t: t[2])
    count = dict((p, 1) for _, p, _ in pres)
    prev_y = 0
    addrs = []
    for i, p, _ in pres:
        addrs.append((i, p * 1000000 + count[p]))
        count[p] += 1
    addrs.sort(key=lambda t: t[0])
    for _, a in addrs:
        print("%012d" % a)

Solution (Python):
n, m = [int(x) for x in input().split()]
l = []
for i in range(m):
    tmp = [int(x) for x in input().split()]
    l.append([i, tmp[0], tmp[1]])
l.sort(key=lambda x: x[2])

prefecture = [0 for _ in range(n)]
city = [[] for _ in range(m)]

for info in l:
    i, p, y = info
    tmp = [p, prefecture[p-1]+1]
    prefecture[p-1] += 1
    city[i] = tmp

for x in city:
    p_str = str(x[0])
    c_str = str(x[1])
    p_add = '0'*(6 - len(p_str))
    c_add = '0' * (6 - len(c_str))
    p_str = p_add + p_str
    c_str = c_add + c_str
    print(p_str + c_str)

Solution (Python):
def main():
    N, M = map(int, raw_input().split())
    PY = [{"Year": 0, "Pre": 0, "id": idx, "ans": ""} for idx in xrange(1, M + 1)]
    cnt = [0] * (N + 1)
    for i in xrange(M):
        PY[i]["Pre"], PY[i]["Year"] = map(int, raw_input().split())

    PY = sorted(PY, key=lambda ele: ele["Year"])

    for i in xrange(M):
        cnt[PY[i]["Pre"]] += 1
        PY[i]["ans"] = str(PY[i]["Pre"]).zfill(6) + str(cnt[PY[i]["Pre"]]).zfill(6)

    PY = sorted(PY, key=lambda ele: ele["id"])
    for ele in PY:
        print(ele["ans"])


if __name__ == "__main__":
    main()

Solution (Python):

from collections import defaultdict

n, m = list(map(int, input().split()))
d = defaultdict(set)
ps = set()
p = []
y = []
for i in range(m):
    pi, yi = list(map(int, input().split()))
    p.append(pi)
    y.append(yi)
    ps.add(pi)
    d[pi].add(yi)

dn = defaultdict(list)
for i in d.keys():
    n = 1
    for j in sorted(d[i]):
        dn[i, j] = n
        n += 1

for i in range(len(p)):
    print('{0:06d}'.format(p[i]), '{0:06d}'.format(dn[p[i], y[i]]), sep='')

Solution (Python):
def c_id(N, M, City):
    City = sorted(City, key=lambda x: (x[0], x[1]))
    
    a, b = City[0][0], 0
    for j, (p, y, k) in enumerate(City):
        if p == a:
            
            b += 1
            City[j] = [p, b, k]
        else:
            
            a = p
            b = 1
            City[j] = [p, b, k]
    city = sorted(City, key=lambda x: x[2])
    

    ans_tmp = []
    for p, q, k in city:
        ans_tmp.append('{0:06d}{1:06d}'.format(p, q))
    ans = '\n'.join(ans_tmp)
    return ans

N, M = [int(i) for i in input().split()]
City = [[int(i) for i in input().split()] + [k] for j, k in enumerate(range(M), 1)]
print(c_id(N, M, City))

Solution (Python):
import copy

def main():
    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, len(ps[p-1]), i))

    ans_ = [0 for _ in range(m)]

    ans =  copy.deepcopy(ps)
    for i in range(n):
        p = ps[i]
        sorted_ps = sorted(p)
        for j, sp in enumerate(sorted_ps):
            ans_[sp[2]] = '{0:06d}'.format(i+1) + '{0:06d}'.format(j+1)

    for r in ans_:
        print(r)



if __name__ == '__main__':
    main()

Solution (Python):
import copy

def main():
    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, len(ps[p-1]), i))

    ans_ = [0 for _ in range(m)]

    ans =  copy.deepcopy(ps)
    for i in range(n):
        p = ps[i]
        sorted_ps = sorted(p)
        for j, sp in enumerate(sorted_ps):
            ans_[sp[2]] = '{0:06d}'.format(i+1) + '{0:06d}'.format(j+1)

    for r in ans_:
        print(r)



if __name__ == '__main__':
    main()

Solution (Python):
import bisect
n,p=map(int,input().split())
arr=[]
arr1=[[] for i in range(100001)]
for i in range(p):
    arr.append(list(map(int,input().split())))
    arr1[arr[i][0]].append(arr[i][1])
for i in range(100001):
    if(len(arr1[i])>1):
        arr1[i].sort()
for i in range(p):
    print("%06d%06d"%(arr[i][0],bisect.bisect_right(arr1[arr[i][0]],arr[i][1])))

Solution (Python):
from sys import stdin

def main():
    N, M = map(int, input().split())
    PY = [tuple(map(int, input().split())) for _ in [0] * M]

    py = sorted(PY, key=lambda x: x[1])
    py.sort()
    num = dict()
    prev = -1
    for v in py:
        current = v[0]
        if prev != current:
            i = 1
        num[v] = i
        i += 1
        prev = current
    for v in PY:
        s = str(v[0]).zfill(6) + str(num[v]).zfill(6)
        print(s)

input = lambda: stdin.readline()
main()

Solution (Python):
from operator import itemgetter
n,m=map(int,input().split())
e=[[int(i) for i in input().split()] for i in range(m)]
for i in range(0,m):
    t=e[i]
    t.append(i)
e.sort()
c=0
k=e[i][0]
for i in range(0,m):
    d=e[i]
    if k==e[i][0]:
        c+=1
        d.append("0"*(6-len(str(k)))+str(k)+"0"*(6-len(str(c)))+str(c))
    else:
        k=e[i][0]
        c=1         
        d.append("0"*(6-len(str(k)))+str(k)+"0"*(6-len(str(c)))+str(c))
e.sort(key=itemgetter(2)) 
for i in range(0,m):
    print(e[i][3])

Solution (Python):
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))

Solution (Python):
n,m=map(int,input().split())
p=[]
for i in range(m):
    a,b=map(int,input().split())
    p.append([i,a,b,0])
ps=sorted(p,key=lambda i:(i[1],i[2]))
cnt=1
for i in range(m):
    if i!=0:
        if ps[i][1]==ps[i-1][1]:
            cnt+=1
            ps[i][3]=cnt
        else:
            ps[i][3]=1
            cnt=1
    else:
        ps[i][3]=1
ps=sorted(ps,key=lambda i:i[0])
for i in range(m):
    print("{0:06d}".format(ps[i][1]),end='')
    print("{0:06d}".format(ps[i][3]))

Solution (Python):
import numpy as np
N, M = [int(a) for a in input().split()]
P = []
Y = []

for _ in range(M):
    p, y =  [int(a) for a in input().split()]
    P.append(p)
    Y.append(y)

index = {}
id = ["" for _ in range(len(P))]

for i in np.argsort(Y):
    index[P[i]] = index.get(P[i], 1)
    id[i] = "{0:06d}".format(P[i])+"{0:06d}".format(index[P[i]])
    index[P[i]] += 1

for i in id:
    print(i)

Solution (Python):
n, m = map(int, input().split())

p = [(list(map(int, input().split())) + [0] + [i]) for i in range(m)]
p_sort = sorted(p, key=(lambda x:x[1]))

index_list = [1] * n
for i in range(m):
    p_sort[i][2] = index_list[p_sort[i][0] - 1]
    index_list[p_sort[i][0] - 1] += 1

p_sort = sorted(p, key = (lambda x:x[3]))

for i in range(m):
    string = str(p_sort[i][0]).zfill(6) + str(p_sort[i][2]).zfill(6)
    print(string)

Solution (Python):
N, M = map(int,input().split())
dic = {}
P = []; Y = []
ans = ["" for i in range(M)]
for i in range(M):
    p, y = map(int,input().split())
    P.append(p)
    Y.append(y)
    if p not in dic:
        dic[p] = [[y,i]]
    else:
        dic[p].append([y,i])

for k,p in dic.items():
    p.sort()
    for pi in range(len(p)):
        ans[p[pi][1]] = "{:06d}{:06d}".format(k,pi+1)

for i in range(M):
    print(ans[i])

Solution (Python):
def run(N, M, PY):
    PY = sorted(PY, key=lambda x: x[1])
    
    ret = {}
    for i in range(len(PY)):
        P = PY[i][0]
        j = PY[i][2]
        if P in ret.keys():
            cnt = ret[P][1]
        else:
            cnt = 0
            ret[P] = [[], cnt]
        cnt += 1
        id = '{0:06d}'.format(P)+'{0:06d}'.format(cnt)
        ret[P][0].append([id, j])
        ret[P][1] += 1
    ret2 = []
    for r in ret.values():
        for id, j in r[0]:
            ret2.append([id, j])
    ret2 = sorted(ret2, key=lambda x: x[1])
    ret3 = []
    for r in ret2:
        ret3.append(r[0])
    return ret3


def main():
    N, M = map(int, input().split())
    PY = []
    for i in range(M):
        tmp = list(map(int, input().split()))
        tmp.append(i)
        PY.append(tmp)
    ret = run(N, M, PY)
    for r in ret:
        print(r)


if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
l = [ [ list(map(int, input().split())), i ] for i in range(M) ]
l.sort(key=lambda x: (x[0][0],x[0][1]))

idx = 1
idx_p = l[0][0]
ans = []
for x in l:
    if x[0][0] == idx_p:
        idx += 1
    else:
        idx = 1
        idx_p = x[0][0]
    ans.append([ x[1], '%06d%06d' % (idx_p, idx)])

ans.sort(key=lambda x: x[0])
for i in ans:
    print(i[1])

Solution (Python):
from operator import itemgetter
import bisect
N, M = map(int, input().split())
data = []
for i in range(M):
    p, y = map(int, input().split())
    data.append([p, y])

database = [[] for i in range(N+1)]
for i in range(M):
    database[data[i][0]].append(data[i][1])
for i in range(1, N+1):
    database[i].sort()

for i in range(M):
    pref = data[i][0]
    number = bisect.bisect_left(database[pref], data[i][1]) + 1
    pref = format(pref, "06")
    number = format(number, "06")
    print(str(pref) + str(number))

Solution (Python):


def main():
    N, M = map(int, raw_input().split(" "))
    answer = [0] * M
    pref = {}
    for i in xrange(M):
        P, Y = map(int, raw_input().split(" "))
        if P not in pref:
            pref[P] = []
        pref[P].append((i, Y))
    for p, arr in pref.items():
        arr.sort(lambda a, b: a[1] - b[1])
        for i in xrange(1, len(arr)+1):
            item = arr[i-1]
            answer[item[0]]  = ("0" * 5 + str(p))[-6:]
            answer[item[0]] += ("0" * 5 + str(i))[-6:]
    for i in xrange(M):
        print answer[i]

if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict


n, m = map(int, input().split())

y = []
dic = {}
for _ in range(m):
    pi, yi = map(int, input().split())
    y.append(yi)
    dic[yi] = pi

d = defaultdict(int)
id_dict = {}

for yi, pi in sorted(dic.items()):
    d[pi] += 1
    id_dict[yi] = '{:0>6}{:0>6}'.format(pi, d[pi])

for yi in y:
    print(id_dict[yi])

Solution (Python):
N, M = list(map(int, input().split()))
Plist = []
L = []
for i in range(M):
	P, Y = list(map(int, input().split()))
	L.append([Y, P, i])
	Plist.append(P)

L = sorted(L)
PL = [0 for i in range(N)]
ML = [0 for i in range(M)]
for i in range(M):
	PL[L[i][1] - 1] += 1
	ML[L[i][2]] = PL[L[i][1] - 1]


for i in range(M):
	plen = len(str(Plist[i]))
	ansP = "0" * (6 - plen) + str(Plist[i])
	mlen = len(str(ML[i]))
	ansM = "0" * (6 - mlen) + str(ML[i])
	print(ansP + ansM)

Solution (Python):
n,m=map(int,input().split())
p=[]
for i in range(m):
    a,b=map(int,input().split())
    p.append([i,a,b,0])
ps=sorted(p,key=lambda i:(i[1],i[2]))
cnt=1
for i in range(m):
    if i!=0:
        if ps[i][1]==ps[i-1][1]:
            cnt+=1
            ps[i][3]=cnt
        else:
            ps[i][3]=1
            cnt=1
    else:
        ps[i][3]=1
ps=sorted(ps,key=lambda i:i[0])
for i in range(m):
    print("{0:06d}".format(ps[i][1]),end='')
    print("{0:06d}".format(ps[i][3]))

Solution (Python):
N,M=map(int, input().split())
PY=[list(map(int, input().split()))+[i] for i in range(M)]
PY=list(sorted(PY))
ls=[]
current=0
ct=1
for i in range(M):
    s1=str(PY[i][0])
    s2=''
    for j in range(6-len(s1)):
        s2+='0'
    s3=s2+s1

    if current==PY[i][0]:
        ct+=1
    else:
        ct=1
        current=PY[i][0]

    s4=str(ct)
    s5=''
    for j in range(6-len(s4)):
        s5+='0'
    s6=s5+s4
    s7=s3+s6

    ls.append([s7,PY[i][2]])

ls=sorted(ls, key=lambda x :x[1])
for i in ls:
    print(i[0])

Solution (Python):
N, M = map(int, input().split())

preds = {}
i = 1
for _ in range(M):
    x, y = input().split(' ')
    preds[i] = (int(x), int(y))
    i += 1


ans = [0 for x in range(M)]

flg = -1
num = 1
for x, y in sorted(preds.items(), key=lambda x: x[1]):
    if flg != y[0]:
        num = 1
        ans[x-1] = str(y[0]).rjust(6, '0') + str(num).rjust(6, '0')
        flg = y[0]
    else:
        num += 1
        ans[x-1] = str(y[0]).rjust(6, '0') + str(num).rjust(6, '0')

for i in ans:
    print(i)

Solution (Python):
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))

Solution (Python):
n,m=map(int,input().split())
p=[]
for i in range(m):
    a,b=map(int,input().split())
    p.append([i,a,b,0])
ps=sorted(p,key=lambda i:(i[1],i[2]))
cnt=1
for i in range(m):
    if i!=0:
        if ps[i][1]==ps[i-1][1]:
            cnt+=1
            ps[i][3]=cnt
        else:
            ps[i][3]=1
            cnt=1
    else:
        ps[i][3]=1
ps=sorted(ps,key=lambda i:i[0])
for i in range(m):
    print("{0:06d}".format(ps[i][1]),end='')
    print("{0:06d}".format(ps[i][3]))

Solution (Python):
n,m=map(int,input().split())
p=[]
for i in range(m):
    a,b=map(int,input().split())
    p.append([i,a,b,0])
ps=sorted(p,key=lambda i:(i[1],i[2]))
cnt=1
for i in range(m):
    if i!=0:
        if ps[i][1]==ps[i-1][1]:
            cnt+=1
            ps[i][3]=cnt
        else:
            ps[i][3]=1
            cnt=1
    else:
        ps[i][3]=1
ps=sorted(ps,key=lambda i:i[0])
for i in range(m):
    print("{0:06d}".format(ps[i][1]),end='')
    print("{0:06d}".format(ps[i][3]))

Solution (Python):
N,M = map(int,input().split())
years = []
for i in range(1,M+1):
    p,y = map(int,input().split())
    years.append((p,y,i))

prefectureOrdering = [1] * (10 ** 5 + 1)
inputOrdering = [False] * (10 ** 5 + 1)

years.sort()

for i in years:
    s = ""
    s += "0" * (6 - len(str(i[0]))) + str(i[0]) + "0" * (6 - len(str(prefectureOrdering[i[0]]))) + str(prefectureOrdering[i[0]])
    prefectureOrdering[i[0]] += 1
    inputOrdering[i[2]] = s

for i in range(1,M+1):
    print(inputOrdering[i])

Solution (Python):
N, M = list(map(int, input().split()))
P = {}
lines = []
for i in range(M):
    p, y = list(map(int, input().split()))
    lines.append((p,y))
    if p in P.keys():
        P[p].append(y)
    else:
        P[p] = [y]

for p, y in P.items():
    tmp = y[:]
    tmp.sort()
    
    P[p] = {}
    for i in range(len(tmp)):
        P[p][tmp[i]] = i

for line in lines:
    p, y = line
    ans = ('00000'+str(p))[-6:] + ('00000'+(str(P[p][y]+1)))[-6:]
    print(ans)

Solution (Python):
n,m=map(int,input().split())
p=[]
for i in range(m):
    a,b=map(int,input().split())
    p.append([i,a,b,0])
ps=sorted(p,key=lambda i:(i[1],i[2]))
cnt=1
for i in range(m):
    if i!=0:
        if ps[i][1]==ps[i-1][1]:
            cnt+=1
            ps[i][3]=cnt
        else:
            ps[i][3]=1
            cnt=1
    else:
        ps[i][3]=1
ps=sorted(ps,key=lambda i:i[0])
for i in range(m):
    print("{0:06d}".format(ps[i][1]),end='')
    print("{0:06d}".format(ps[i][3]))

Solution (Python):
N,M=map(int, raw_input().split())
P=[]

for i in range(M):
	x,y=map(int, raw_input().split()) 
	P.append( [i,x,y] )



P.sort(key=lambda x:(x[1],x[2]))


prev_y=None
for idx,t in enumerate(P):
	x=t[0]; y=t[1]; z=t[2]

	if prev_y is None:
		cnt=1
	elif y!=prev_y:
		cnt=1
	else:
		cnt+=1

	P[idx].append(  "0"* (6-len(str(y)))+str(y)+"0"* (6-len(str(cnt)))+str(cnt) ) 

	prev_y=y

	

P.sort(key=lambda x:x[0] )


for x,y,z,w  in P:
	print w

Solution (Python):
N, M = map(int, input().split())

preds = {}
i = 1
for _ in range(M):
    x, y = input().split(' ')
    preds[i] = (int(x), int(y))
    i += 1


ans = [0 for x in range(M)]

flg = -1
num = 1
for x, y in sorted(preds.items(), key=lambda x: x[1]):
    if flg != y[0]:
        num = 1
        ans[x-1] = str(y[0]).rjust(6, '0') + str(num).rjust(6, '0')
        flg = y[0]
    else:
        num += 1
        ans[x-1] = str(y[0]).rjust(6, '0') + str(num).rjust(6, '0')

for i in ans:
    print(i)

Solution (Python):
n,m=map(int,input().split())
p=[]
for i in range(m):
    a,b=map(int,input().split())
    p.append([i,a,b,0])
ps=sorted(p,key=lambda i:(i[1],i[2]))
cnt=1
for i in range(m):
    if i!=0:
        if ps[i][1]==ps[i-1][1]:
            cnt+=1
            ps[i][3]=cnt
        else:
            ps[i][3]=1
            cnt=1
    else:
        ps[i][3]=1
ps=sorted(ps,key=lambda i:i[0])
for i in range(m):
    print("{0:06d}".format(ps[i][1]),end='')
    print("{0:06d}".format(ps[i][3]))

Solution (Python):



i = input().split(' ')
n = int(i[0])
m = int(i[1])
pys = [] 
for j in range(m):
  i = input().split(' ')
  pys.append((j+1, int(i[0]), int(i[1])))

pys.sort(key=lambda py: py[2])
pys.sort(key=lambda py: py[1])

yno = 1
pbef = pys[0][1]
cityids = []
for cityno, p, y in pys:
  if p != pbef:
    pbef = p
    yno = 1
  cityid = "{0:06d}{1:06d}".format(p, yno)
  cityids.append((cityno, cityid))
  yno += 1
cityids.sort(key=lambda cityid:cityid[0]) 
for cityid in cityids:
  print(cityid[1])

Solution (Python):
N, M = map(int, input().split())
A = []
Plst = [list() for _ in range(N)]
dic = {}
for i in range(M):
    P, Y = map(int, input().split())
    A.append([i, P, Y])
    Plst[P - 1].append(Y)
    dic[(P, Y)] = 0
for i in range(N):
    Plst[i].sort()
    for j in range(len(Plst[i])):
        s = str(str(i + 1).zfill(6) + str(j + 1).zfill(6))
        dic[(i, Plst[i][j])] = s
for e in A:
    print(dic[(e[1] - 1, e[2])])

Solution (Python):
inputs = raw_input().replace("\n", "").split(" ")
N, M = map(int, inputs)

P_list = [[] for _ in xrange(N)]

PY_pairs = []
for _ in xrange(M):
    inputs = raw_input().replace("\n", "").split(" ")
    Pi, Yi = map(int, inputs)
    P_list[Pi-1].append(Yi)
    PY_pairs.append((Pi, Yi))

cvt_dict = {}
for Pi in xrange(N):
    for output_i, (input_i, Yi) in enumerate(sorted(enumerate(P_list[Pi]), key=lambda x: x[1])):
        address = "%06d" % (Pi + 1) + "%06d" % (output_i + 1) 
        cvt_dict[(Pi+1, Yi)] = address

for Pi, Yi in PY_pairs:
    print cvt_dict[(Pi, Yi)]

Solution (Python):
import sys

def 解():
    iN,iM = [int(_) for _ in input().split()]
    aPM = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]
    dC = {}
    def addCity(d,p,m,i):
        if p in d:
            d[p].append((m,i))
        else:
            d[p]=[(m,i)]

    iIndex = 1
    for p,m in aPM:
        addCity(dC,p,m,iIndex)
        iIndex += 1
    oAns = []

    for iCity in dC.keys():
        iIndex = 1
        for m,i in sorted(list(dC[iCity])):
            oAns.append((i,'{:06}{:06}'.format(iCity,iIndex)))
            iIndex += 1
    oAns.sort()
    oAns2 =[]
    for i,s in oAns:
        oAns2.append(s)
    print("\n".join(oAns2))
解()

Solution (Python):
import sys,collections,math;sys.setrecursionlimit(10**7)
from operator import itemgetter;
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,M = Is()
lis = []
for i in range(M):
    lis.append([i]+Is())
t = sorted(lis,key=itemgetter(1,2))
x,p = 0,1
for i in range(M):
    if p == t[i][1]:
        x += 1
        t[i] += [p,x]
    else:
        p = t[i][1]
        x = 1
        t[i] += [p,x]
t = sorted(t,key=itemgetter(0))
for e in t:
    print( (6-len(str(e[3])))*"0" + str(e[3]) + (6-len(str(e[4])))*"0" + str(e[4]))

Solution (Python):
from bisect import bisect_left

n, m = map(int, input().split())
qs = [list(map(int, input().split())) for _ in range(m)]
pys = [[] for _ in range(n)]
for q in qs:
    p, y = q
    p -= 1
    pys[p].append(y)

for i in range(n):
    pys[i] = sorted(pys[i])

for q in qs:
    p, y = q
    p -= 1
    number = bisect_left(pys[p], y) + 1

    print(str(p + 1).zfill(6) + str(number).zfill(6))

Solution (Python):
N, M = map(int, input().split())
Pref = [1 for i in range(N)]
City = []
Ans = ["" for i in range(M)]
for i in range(M):
    p, y = map(int, input().split())
    City.append((y, p-1, i))
City.sort()
for i in range(M):
    Ans[City[i][2]] =  "{0:06d}".format(City[i][1]+1) + "{0:06d}".format(Pref[City[i][1]])
    Pref[City[i][1]] += 1

for i in range(M):
    print(Ans[i])

Solution (Python):
N, M = map(int, input().split())
dt = {}

ans = {}


towns = []
for _ in range(M):
    p, y = map(int, input().split())
    if dt.get(p):
        dt[p].append(y)
    else:
        dt[p] = [y]
    towns.append((p, y))

for key in dt.keys():
    for i, item in enumerate(sorted(dt[key]), 1):
        ans[(key, item)] = i

for town in towns:
    num = ans[town]
    print("{0:06}{1:06}".format(town[0], num))

Solution (Python):
def helper(s):
    return '0' * (6 - len(s)) + s

def main():
    n, m = map(int, input().split())
    cities = []
    counts = [1] * (n + 1)
    for i in range(m):
        a, b = input().split()
        cities.append([a, int(b), i, ''])
    cities.sort(key = lambda j: j[1])
    for i in range(m):
        temp = cities[i]
        cities[i][3] = helper(temp[0]) + helper(str(counts[int(temp[0])]))
        counts[int(temp[0])] += 1
    cities.sort(key = lambda j: j[2])
    for i in cities:
        print(i[3])
    return 0
main()

Solution (Python):
(N, M) = map(int, input().split())

P = []
Y = []
pyd = {}
for i in range(M):
    (p, y) = map(int, input().split())
    if p in pyd:
        pyd[p].append([y, i])
    else:
        pyd[p] = [[y, i]]

ans = []
for k in pyd:
    pyd[k].sort(key=lambda x:x[0])
    for i in range(len(pyd[k])):
        htag = str(k)
        while len(htag) < 6:
            htag = '0' + htag
        ltag = str(i+1)
        while len(ltag) < 6:
            ltag = '0' + ltag
        tag = htag + ltag
        ans.append([pyd[k][i][1], tag])

ans.sort(key=lambda x:x[0])
for a in ans:
    print(a[1])

Solution (Python):
import sys

def 解():
    iN,iM = [int(_) for _ in input().split()]
    aPM = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]
    dC = {}
    def addCity(d,p,m,i):
        if p in d:
            d[p].append((m,i))
        else:
            d[p]=[(m,i)]

    iIndex = 1
    for p,m in aPM:
        addCity(dC,p,m,iIndex)
        iIndex += 1
    oAns = []

    for iCity in dC.keys():
        iIndex = 1
        for m,i in sorted(list(dC[iCity])):
            oAns.append((i,'{:06}{:06}'.format(iCity,iIndex)))
            iIndex += 1
    oAns.sort()
    oAns2 =[]
    for i,s in oAns:
        oAns2.append(s)
    print("\n".join(oAns2))
解()

Solution (Python):
N,M = map(int,input().split())
PY = [[int(py) for py in input().split()] for _ in range(M)]

for i in range(1,M+1):
    PY[i-1].append(i)

PY.sort(key=lambda x:x[1])

count = [1 for _ in range(N)]

ans = []

for cell in PY:
    row = '{0:06d}'.format(cell[0]) + '{0:06d}'.format(count[cell[0]-1])
    ans.append([row,cell[2]])
    count[cell[0]-1] += 1


ans.sort(key=lambda x:x[1])

for row in ans:
    print(row[0])

Solution (Python):
N, M = map(int, input().split())
P = []
Y = []
for i in range(M):
    p, y = map(int, input().split())
    P.append(p)
    Y.append(y)

A = [[] for i in range(N)]

for i in range(M):
    A[P[i]-1].append([i, Y[i]])
    
for i in range(N):
    A[i] = sorted(A[i], key=lambda x:x[1])

R = [[] for i in range(M)]

cc = 0
for i in range(N):
    c = 1
    for j in A[i]:
        R[j[0]] = str(10**12 + (i+1) * (10**6) + c)[1:]
        c += 1
        cc += 1
for r in R:
    print(r)

Solution (Python):
import copy
n,m=map(int, input().split(" "))
d={}
for i in range(m):
    p,y=map(int, input().split(" "))
    d[i]=10**10*p+y


d2={}
dct=sorted(d.items(), key=lambda x: x[1])

init=-999

count=1
for k, v in dct:
    pref=str(v//10**10)
    if pref != init:
        count=1
    else:
        count+=1

    in_pref=str(pref)
    in_count=str(count)
    while len(in_pref)!=6:
        in_pref="0"+in_pref
    while len(in_count)!=6:
        in_count="0"+in_count

    init=pref
    d2[k]=in_pref+in_count

dct2=sorted(d2.items(), key=lambda x: x[0])
for k, v in dct2:
    print(v)

Solution (Python):
def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict
P = defaultdict(lambda: [])
S = []
N,M = inpl()
for i in range(M):
    np,ny = inpl()
    P[np].append([ny,i+1,np,0])

for j in P.values():
    j = sorted(j,key = lambda x: x[0])
    for i in range(len(j)):
        j[i][3] = i+1
        S.append(j[i])
S = sorted(S,key = lambda x: x[1])
for ny,num,np,x in S:
    ans = '0'*(6-len(str(np))) + str(np)\
    + '0'*(6-len(str(x))) + str(x)
    print(ans)

Solution (Python):
from collections import defaultdict
import numpy as np

[n, m] = list(map(int, input().split()))
py = [list(map(int, input().split())) for _ in range(m)]

d = defaultdict(int)
py = np.array(py)
argsort = np.argsort(py[:, 1])
t = []
for [p, y] in py[argsort]:
    d[p] += 1
    t.append(d[p])
t = np.array(t)[np.argsort(argsort)]

for [p, y], t in zip(py, t):
    print('{0:06d}{1:06d}'.format(p, t))

Solution (Python):
N, M = map(int, input().split())
cities = []
for cNo in range(M):
    P, Y = map(int, input().split())
    cities.append((Y, P, cNo))

cities.sort()

IDs = ['' for _ in range(M)]
nums = [0] * (N + 1)
for Y, P, cNo in cities:
    nums[P] += 1
    IDs[cNo] = str(P).zfill(6) + str(nums[P]).zfill(6)

print('\n'.join(IDs))

Solution (Python):
n,m=map(int,input().split())

d=[[] for i in range(n)]
ans=[]
for i in range(m):
    p,y=map(int,input().split())
    d[p-1].append((y,i))
for a,i in enumerate(d):
    i.sort()
    for b,j in enumerate(i):
        c=str(a+1)
        d=str(b+1)
        c="0"*(6-len(c))+c
        d="0"*(6-len(d))+d
        ans.append((j[1],c+d))
ans.sort()
for i in ans:
    print(i[1])

Solution (Python):
def main():
    """
    1 <= N  <= 10^5
    1 <= M  <= 10^5
    0 <= Pi <= N
    0 <= Yi <= 10^9
    Yi != Yj
    """
    N, M = map(int, input().split())
    P, Y = zip(*(
        map(int, input().split())
        for _ in range(M)
    ))

    ans = f(N, M, P, Y)
    print(*ans, sep="\n")


def f(N, M, P, Y):
    piy = [[] for _ in range(N)]
    for i, (p, y) in enumerate(zip(P, Y), 1):
        piy[p-1].append((p, i, y))

    ns = []
    for vs in piy:
        sorted_vs = sorted(vs, key=lambda x: x[2])
        for k, (p, i, _) in enumerate(sorted_vs, 1):
            n = "{:06d}{:06}".format(p, k)
            ns.append((i, n))

    ans = [n for _, n in sorted(ns, key=lambda x: x[0])]

    return ans


if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
inputDict = {}  
ansDict = {}  
inputOrderList = []  
cityCountDict = {}  

for index in range(M):
    Pi, Yi = map(int, input().split())
    inputOrderList.append(Yi)
    inputDict[Yi] = Pi
    cityCountDict[Pi] = 1

for year, pref in sorted(inputDict.items()):
    num = cityCountDict[pref]
    ansDict[year] = "{0:06d}".format(pref) + "{0:06d}".format(num)
    cityCountDict[pref] += 1

for order in inputOrderList:
    print(ansDict[order])

Solution (Python):
n,m=[int(s)for s in input().split()]
pref={}
yn={}
res=[-1 for _ in range(m)]
for i in range(m):
    p,y=[int(s)for s in input().split()]
    if p not in pref:pref[p]=[]
    pref[p].append(y)
    yn[y]=i
for p in pref:
    pref[p]=sorted(pref[p])
    for i in range(len(pref[p])):
        num="%06d%06d"%(p,i+1)
        res[yn[pref[p][i]]]=num
for s in res:print(s)

Solution (Python):
n,m=map(int,input().split())

d=[[] for i in range(n)]
ans=[]
for i in range(m):
    p,y=map(int,input().split())
    d[p-1].append((y,i))
for a,i in enumerate(d):
    i.sort()
    for b,j in enumerate(i):
        c=str(a+1)
        d=str(b+1)
        c="0"*(6-len(c))+c
        d="0"*(6-len(d))+d
        ans.append((j[1],c+d))
ans.sort()
for i in ans:
    print(i[1])

Solution (Python):
N, M = map(int, input().split())
x = []

for i in range(M):
    x.append(list(map(int, input().split()))+[i])

x.sort()
y = []
prv_p = -1
idx = 1
for xx in x:
    if prv_p != xx[0]:
        prv_p = xx[0]
        idx = 1
    y.append([xx[-1],'{0:06d}{1:06d}'.format(xx[0], idx)])
    idx += 1

y.sort()
for yy in y:
    print(yy[1])

Solution (Python):
n, m = map(int, input().split())




id_dic = {}
city_num = []
for i in range(m):
    p, y = map(int, input().split())
    city_num.append((p, y))
    if p not in id_dic:
        id_dic[p] = []
    id_dic[p].append(y)

for p in id_dic.keys():
    id_dic[p].sort()

ans = {}
for p in id_dic.keys():
    for i, y in enumerate(id_dic[p]):
        ans[(p, y)] = i + 1

for p, y in city_num:
    num = ans[(p, y)]

    print("{:0>6}".format(p) + "{:0>6}".format(num))

Solution (Python):
from operator import itemgetter

li = list(map(int, input().split()))
N = li[0]
M=li[1]
L = []
K=[]
for i in range(N):
    L.append([])
    

for i in range(M):
    li = list(map(int, input().split()))
    L[li[0] - 1].append([li[1], i])
    K.append(0)

for i in range(N):
        O = L[i]

        O.sort()
        for j in range(len(O)):
                K[O[j][1]]=str(i+1).zfill(6)+str(j+1).zfill(6)

for i in range(M):
        print(K[i])