Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1

n,m = map(int, input().split())
  
if m % n == 0:
  print(m//n)
  exit()
  
elif is_prime(m):
  print(1)
  
else:
  i = m // n
  ans = 0
  while i  >= 1:
    if (m - i * n) % i == 0:
      ans = i
      break
    i -= 1

  print(ans)

### FIXED CODE ###

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

ans = 1

for i in range(1, int(m ** 0.5)+1):
  if m % i == 0:
    if i >= n:
      ans = max(ans, m // i)
    elif m // i >= n:
      ans = max(ans, i)
      
      
print(ans)
### BUGGY CODE ###

import math
N,K=map(int,input().split())
A=list(map(int,input().split()))
def check(x):
  if x==0:
    return 0
  else:
    t=0
    for i in range(N):
      t+=math.ceil(A[i]/x)-1
    if t<=K:
      return 10
    else:
      return 0
low=0
high=max(A)
sig=(low+high)//2
while True:
  if check(sig)==10:
    if check(sig-1)==0:
      ans=sig
      break
    else:
      high=sig-1
      sig=(low+sig)//2
  else:
    low=sig+1
    sig=(high+sig)//2
print(ans)


### FIXED CODE ###

import math
N,K=map(int,input().split())
A=list(map(int,input().split()))
def check(x):
  if x==0:
    return 0
  else:
    t=0
    for i in range(N):
      t+=math.ceil(A[i]/x)-1
    if t<=K:
      return 10
    else:
      return 0
low=0
high=max(A)
sig=(low+high)//2
tf=0
if K==0:
  tf=1
  ans=high
while tf==0:
  if check(sig)==10:
    if check(sig-1)==0:
      ans=sig
      break
    else:
      high=sig-1
      sig=(low+high)//2
  else:
    low=sig+1
    sig=(high+low)//2
print(ans)
### BUGGY CODE ###

n = int(input())
hoge = [int(input()) for i in range(n)]

max_list = []
for i in range(len(hoge)):
    temp = hoge.copy()
    del temp[i]
    max_value = max(temp)
    max_list.append(max_value)
for i in max_list:
    print(i)

### FIXED CODE ###

n = int(input())
hoge = [int(input()) for i in range(n)]
max_value = max(hoge)
second_value = sorted(hoge)[-2]
if max_value == second_value:
    for i in range(len(hoge)):
        print(max_value)
else:
    for i in hoge:
        if i != max_value:
            print(max_value)
        else:
            print(second_value)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

H, W = map(int, input().split())

a = []
for i in range(H):
    a.append(str(input()))

R = [[0] * W for i in range(H)]
L = [[0] * W for i in range(H)]
D = [[0] * W for i in range(H)]
U = [[0] * W for i in range(H)]

for i in range(H):
    cur = 0
    for j in range(W):
        if a[i][j] == "#":
            cur = 0
            U[i][j] = 0
        else:
            cur += 1
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] += U[i-1][j] + 1
        L[i][j] = cur

ans = 0
for i in reversed(range(H)):
    cur = 0
    for j in reversed(range(W)):
        if a[i][j] == "#":
            cur = 0
            D[i][j] = 0
        else:
            cur += 1
            if i == (H-1):
                D[i][j] = 1
            else:
                D[i][j] += D[i+1][j] + 1
        R[i][j] = cur
        if L[i][j] + R[i][j] + D[i][j] + U[i][j] -3 > ans:
            ans = L[i][j] + R[i][j] + D[i][j] + U[i][j] -3

print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline

H, W = map(int, input().split())

a = []
for i in range(H):
    a.append(str(input()))

R = [[0] * W for i in range(H)]
L = [[0] * W for i in range(H)]
D = [[0] * W for i in range(H)]
U = [[0] * W for i in range(H)]

for i in range(H):
    cur = 0
    for j in range(W):
        if a[i][j] == "#":
            cur = 0
            U[i][j] = 0
        else:
            cur += 1
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] += U[i-1][j] + 1
        L[i][j] = cur

ans = 0
for i in reversed(range(H)):
    cur = 0
    for j in reversed(range(W)):
        if a[i][j] == "#":
            cur = 0
            D[i][j] = 0
        else:
            cur += 1
            if i == (H-1):
                D[i][j] = 1
            else:
                D[i][j] += D[i+1][j] + 1
        R[i][j] = cur
        if L[i][j] + R[i][j] + D[i][j] + U[i][j] -3 > ans:
            ans = L[i][j] + R[i][j] + D[i][j] + U[i][j] -3

print(ans)
### BUGGY CODE ###

N, M = map(int,input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)

E = []
for v in G[0]:
    if v in E:
        continue
    E.append(v)
    for v2 in G[v]:
        if v2 in E:
            continue
        E.append(v2)

if (N-1) in E:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

N, M = map(int,input().split())
S = [False for _ in range(N)]
G = [False for _ in range(N)]
for _ in range(M):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    if a == 0 and b == N - 1:
        print("POSSIBLE")
        exit()
    if a == 0:
        if G[b]:
            print("POSSIBLE")
            exit()
        S[b] = True
    if b == N - 1:
        if S[a]:
            print("POSSIBLE")
            exit()
        G[a] = True

print("IMPOSSIBLE")
### BUGGY CODE ###

k,s=map(int,input().split())
ans=0
for i in range(s+1):
  for j in range(i,s+1):
    if i<=k and j-i<=k and s-j<=k:
      ans+=1
print(ans)

### FIXED CODE ###

k,s=map(int,input().split())
ans=0
for i in range(s+1):
  for j in range(i,s+1):
    if i<=k and j-i<=k and s-j<=k:
      ans+=1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
INF = 0

class MaxSegTree:
    """
    0-indexed
    query : [L, R)
    """
    def __init__(self, size):
        self.size = 1 << (size.bit_length())  # 完全二分木にする
        self.data = [-INF] * (2 * self.size - 1)

    def build(self, rawData):
        self.data[self.size - 1: self.size - 1 + len(rawData)] = rawData
        for i in range(self.size - 1)[:: -1]:
            self.data[i] = max(self.data[2 * i + 1], self.data[2 * i + 2])

    def update(self, index, value):
        index += self.size - 1
        if self.data[index] >= value:
            return
        self.data[index] = value
        while index >= 0:
            index = (index - 1) // 2
            self.data[index] = max(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, left, right):
        L = left + self.size
        R = right + self.size
        ret = -INF
        while L < R:
            if R & 1:
                R -= 1
                ret = max(ret, self.data[R - 1])
            if L & 1:
                ret = max(ret, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
mxA = max(A)
tree = MaxSegTree(mxA + 10)

for a in A:
    nx = tree.query(max(0, a - K), min(mxA + 1, a + K + 1))
    tree.update(a, nx + 1)

print(tree.query(0, mxA + 1))


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
INF = 0

class MaxSegTree:
    """
    0-indexed
    query : [L, R)
    """
    def __init__(self, size):
        self.size = 1 << (size.bit_length())  # 完全二分木にする
        self.data = [-INF] * (2 * self.size - 1)

    def build(self, rawData):
        self.data[self.size - 1: self.size - 1 + len(rawData)] = rawData
        for i in range(self.size - 1)[:: -1]:
            self.data[i] = max(self.data[2 * i + 1], self.data[2 * i + 2])

    def update(self, index, value):
        index += self.size - 1
        if self.data[index] >= value:
            return
        self.data[index] = value
        while index >= 0:
            index = (index - 1) // 2
            self.data[index] = max(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, left, right):
        L = left + self.size
        R = right + self.size
        ret = -INF
        while L < R:
            if R & 1:
                R -= 1
                ret = max(ret, self.data[R - 1])
            if L & 1:
                ret = max(ret, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
mxA = max(A)
tree = MaxSegTree(mxA + 10)

for a in A:
    nx = tree.query(max(0, a - K), min(mxA + 1, a + K + 1))
    tree.update(a, nx + 1)

print(tree.query(0, mxA + 1))
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(N):
    ans += i
print(ans)

### FIXED CODE ###

N = int(input())
print(((N-1)*N)//2)
### BUGGY CODE ###

def main():
    N = int(input()) # 5人
    An = list(map(int, input().split(' '))) # A2, A3,...
    
    # N = 5
    # An = [1, 1, 2, 2]
    
    # N = 7
    # An = [1, 2, 3, 4, 5, 6]

    # NUM = An.copy()
    # out = []
    # counter = []
    
    # start_index = 0
    
    # for n in range(1, N+1):
    #     count = 0
    #     for an in An[start_index:]:
    #         if n >= an:
    #             if len(NUM) > 0:
    #                 count += 1
    #                 start_index += 1
    #                 NUM = An[start_index:]
    #             # print(n, an, NUM)
    #     counter.append(count)
    #     # out.append(count)
        
    #     # print('counter:', counter, 'out:', out)
        
    # # print('counter:', counter)
    
    counter = []
    count = 0
    start_index = 0
    
    for n in range(1, N+1):
        an = An[start_index:]
        for a in an:
            a -= n
            if a == 0:
                count += 1        
        counter.append(count)
        count = 0
                
        
        
        
        
    
    
    for i in counter:
        print(i)
            


    
main()


### FIXED CODE ###

from collections import Counter


def main():
    N = int(input()) # 5人
    An = list(map(int, input().split(' '))) # A2, A3,...
    
    # N = 10
    # An = [1,1, 1, 1, 1, 1, 1, 1, 1]
    
    # out = [0] *
    
    an = Counter(An)
    for n in range(1, N+1):  
        print(an[n])
            


    
main()
### BUGGY CODE ###

N=int(input())
P=list(map(int,input().split()))
count=0
flag=True
for i in range(N):
    for k in range(1):
        l=min(P[:i+1])
        if P[i]>l:
            flag=False
            break
    if flag:
        count+=1
    else:
        flag=True
print(count)

### FIXED CODE ###

N=int(input())
P=list(map(int,input().split()))
count=1
min=P[0]
for i in range(1,N):
    if min>P[i]:
      count+=1
      min=P[i]
print(count)
### BUGGY CODE ###

from collections import deque

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

path = [[0] * n for _ in range(n)]
dist = [-1] * n
signs = [-1] * n

for i in range(m):
    a, b = map(int, input().split())
    path[a - 1][b - 1] = 1
    path[b - 1][a - 1] = 1

q = deque()
dist[0] = 0
q.append(0)

while len(q) != 0:
    node = q.popleft()

    for i in range(n):
        if path[node][i] == 0:
            continue
        if dist[i] != -1:
            continue
        dist[i] = dist[node] + 1
        q.append(i)

for i in range(1, n):
    for j in range(n):
        if dist[i] - 1 == dist[j]:
            signs[i] = j + 1
            break
        if j == n - 1:
            print('No')
            exit()

for i in range(n):
    if i == 0:
        print('Yes')
    else:
        print(signs[i])

### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())

adjacent_list = [[] for _ in range(n + 1)]

for i in range(m):
    a, b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)

signs = [-1 for _ in range(n + 1)]

que = deque()
que.append(1)

while que:
    node = que.popleft()
    for i in adjacent_list[node]:
        if signs[i] == -1:
            que.append(i)
            signs[i] = node


print('Yes')
for i in range(2, n + 1):
    print(signs[i])
### BUGGY CODE ###

n = int(input())

ans = 0

a, b = 1, 1
for a in range(1, n):
	for b in range(1, n//a + 1):
		if a * b < n:
			ans += 1
print(ans)

### FIXED CODE ###

n = int(input())

ans = 0

for a in range(1, n):
	if n % a == 0:
		ans += n // a - 1
	else:
		ans += n // a
print(ans)
### BUGGY CODE ###

import operator as op

N = int(input())
A = list(map(int, input().split()))

L = []

for a in A:
    L.append([A.index(a) + 1, a])

L.sort(key=op.itemgetter(1))

ans = str()
for l in L:
    ans += str(l[0])
    if l[1] != N:
        ans += " "
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))

L = [0] * N

for i, a in enumerate(A):
    L[a-1] = i + 1

print(*L)
### BUGGY CODE ###

import itertools
n = int(input())
s = list(map(int, input()))
a = tuple(set(itertools.combinations(s, 3)))
ans = len(a)
print(ans)


### FIXED CODE ###

n = int(input())
s = tuple(map(int, input()))
f = [
    [] for i in range(10)
]
ans = 0

for i in range(n-2):
    if len(f[s[i]]) != 0:
        continue
    else:
        for j in range(i+1, n-1):
            if s[j] in f[s[i]]:
                continue
            else:
                f[s[i]].append(s[j])
                a = tuple(set(s[j+1:]))
                ans += len(a)

print(ans)
### BUGGY CODE ###

import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

n = int(input())
list_ABC = [ list(map(int,input().split(" "))) for i in range(n-1)]
q, k = map(int, input().split())
list_XY = [ list(map(int,input().split(" "))) for i in range(q)]

ma = [[0]*n for _ in range(n)]
for a, b, c in list_ABC:
    ma[a-1][b-1] = c
    ma[b-1][a-1] = c

a = csr_matrix(ma)
b = dijkstra(a, directed=False).astype(int)

for x, y in list_XY:
    print(b[x-1,k-1]+b[k-1,y-1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)
 
N = int(input())
ABC = [list(map(int, input().split())) for i in range(N-1)]
Q, K = map(int, input().split())
D = [0] * (N+1)
L = [[] for i in range(N+1)]
for a, b, c in ABC:
    L[a].append([b, c])
    L[b].append([a, c])
 
 
def dfs(n, np):
    for nc in L[n]:
        if nc[0] == np:
            continue
        else:
            D[nc[0]] = D[n] + nc[1]
            dfs(nc[0], n)
 
 
dfs(K, 0)
for i in range(Q):
    x, y = map(int, input().split())
    print(D[x] + D[y])
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]

ans = 0
li_ans = []

primeN = []
tmp = 2
for i in range(2, 100000):
    if primeN:
        for j in range(len(primeN)):
            if i % primeN[j] == 0:
                break
            else:
                if j == len(primeN) - 1:
                    primeN.append(i)
    else:
        if 100000 > tmp:
            primeN.append(i)

for i in primeN:
    for num in a:
        ans += i % num
    else:
        li_ans.append(ans)
        ans = 0
else:
    print(max(li_ans))


### FIXED CODE ###

import fractions
from functools import reduce
 
 
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
 
 
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
 
 
n = int(input())
a = [int(i) for i in input().split()]
 
ans1 = 0
 
lcm = lcm_list(a)
 
for num in a:
    ans1 += (lcm - 1) % num
 
print(ans1)
### BUGGY CODE ###

N = int(input())

S = []

for i in range(N):
  S.append(input())

set_S = list(set(S))
ans = []
for i in range(len(set_S)):
  cnt = 0
  for j in range(N):
    if set_S[i] == S[j]:
      cnt += 1
  temp = [set_S[i],cnt]
  ans.append(temp)

max_cnt = 0
for i in range(len(set_S)):
  if ans[i][1] > max_cnt:
    max_cnt = ans[i][1]

ans_f = []

for i in range(len(set_S)):
  if ans[i][1] == max_cnt:
    ans_f.append(ans[i][0])

ans_f.sort()

for i in range(len(ans_f)):
  print(ans_f[i])

### FIXED CODE ###

N = int(input())

d = {}

for _ in range(N):
  S = input()
  if S in d:
    d[S] += 1
  else:
    d[S] = 1

m = max(d.values())

for s in sorted(k for k in d if d[k] == m):
  print(s)
### BUGGY CODE ###

def main():
    n, m = map(int,input().split())
    s = input()
    t = input()

    l = n * m // gcd(n,m)

    nlist = [0 for i in range(n)]
    mlist = [0 for i in range(m)]
    for i in range(n):
        nlist[i] =  i*l//n

    for i in range(m):
        mlist[i] =  i*l//m

    src_set = set(nlist)
    tag_set = set(mlist)
    matched_list = list(src_set.intersection(tag_set))

    for i in matched_list:
        s_index = nlist.index(i)
        t_index = mlist.index(i)

        if s[s_index] != t[t_index]:
            print("-1")
            exit()

    print(l)

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

if __name__ == "__main__":
        main()


### FIXED CODE ###

def main():
    n, m = map(int,input().split())
    s = input()
    t = input()

    l = n * m // gcd(n,m)

    nlist = [0 for i in range(n)]
    mlist = [0 for i in range(m)]
    for i in range(n):
        nlist[i] =  i*l//n

    for i in range(m):
        mlist[i] =  i*l//m

    src_set = set(nlist)
    tag_set = set(mlist)
    matched_list = list(src_set.intersection(tag_set))

    for i in matched_list:
        s_index = nlist.index(i)
        t_index = mlist.index(i)

        if s[s_index] != t[t_index]:
            print("-1")
            exit()

    print(l)

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

if __name__ == "__main__":
        main()
### BUGGY CODE ###

from collections import defaultdict
g = defaultdict(list)

n, m = map(int, input().split())
if m==0:
    print('Yes')
    exit()
for i in range(m):
    l, r, d = map(int, input().split())
    g[l].append((r, d))
    g[r].append((l, -1*d))
    
visited = {}
vv = {k:None for k in g.keys()}
def dfs(v):
    stack = []
    visited[v] = True
    stack.append((v,0))
    while len(stack)!= 0:
        v,w = stack.pop()
        vv[v] = w
        for c,d in g[v]:
            if not visited.get(c, False):
                visited[c] = True
                stack.append((c,w+d))

f = list(g.keys())[0]
while True:
    dfs(f)
    not_visited = list(set(g.keys()) - set(visited.keys()))
    if not_visited == []: break
    else: f = not_visited[0]

for k in g.keys():
    v = vv[k]
    for c,w in g[k]:
        if not v + w == vv[c]:
            print('No')
            exit()

print('Yes')

### FIXED CODE ###

from collections import defaultdict
g = defaultdict(list)

n, m = map(int, input().split())
if m==0:
    print('Yes')
    exit()
for i in range(m):
    l, r, d = map(int, input().split())
    g[l].append((r, d))
    g[r].append((l, -1*d))
    
visited = {}
vv = {k:None for k in g.keys()}
def dfs(v):
    stack = []
    visited[v] = True
    stack.append((v,0))
    while len(stack)!=0:
        v,w = stack.pop()
        vv[v] = w
        for c,d in g[v]:
            if not visited.get(c, False):
                visited[c] = True
                stack.append((c,w+d))

for f in g.keys():
    if not visited.get(f):
        dfs(f)

for k in g.keys():
    v = vv[k]
    for c,w in g[k]:
        if not v + w == vv[c]:
            print('No')
            exit()

print('Yes')
### BUGGY CODE ###

n ,k = map(int,input().split())
a = list(map(int,input().split()))
max_i = 0
max_d = 0

for i in range(n - k + 1):
    d = 0
    for j in range(k):
        d += a[i + j]
    if d > max_d:
        max_i = i
        max_d = d
ans = 0
for i in range(max_i,max_i + k):
    ans += (1 + a[i])/2
print(ans)  

### FIXED CODE ###

n ,k = map(int,input().split())
a = list(map(int,input().split()))

max_d = sum(a[0:k])
max_i = 0
total = sum(a[0:k])


for i in range(1,n - k + 1):
    total = total - a[i - 1] + a[i + k - 1]

    if total > max_d:
        max_d = total
        max_i = i

ans = 0
for i in range(max_i,max_i + k):
    ans += (1 + a[i])/2
print("{:7f}".format(ans))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
h,w=map(int,input().split())
a=[]
for i in range(h):
    a.append(list(map(int,input().split())))
b=[]
for i in range(h):
    b.append(list(map(int,input().split())))
dp=[[set([]) for i in range(w)] for j in range(h)]
dp[0][0].add(a[0][0]-b[0][0])
dp[0][0].add(b[0][0]-a[0][0])
for i in range(h):
    for j in range(w):
        if i==j==0:
            continue
        if i==0:
            for k in dp[i][j-1]:
                if k<=4000:
                    dp[i][j].add(abs(k+a[i][j]-b[i][j]))
                    dp[i][j].add(abs(k+b[i][j]-a[i][j]))
        elif j==0:
            for k in dp[i-1][j]:
                if k<=4000:
                    dp[i][j].add(abs(k+a[i][j]-b[i][j]))
                    dp[i][j].add(abs(k+b[i][j]-a[i][j]))
        else:
            for k in (dp[i][j-1]|dp[i-1][j]):
                if k<=6500:
                    dp[i][j].add(abs(k+a[i][j]-b[i][j]))
                    dp[i][j].add(abs(k+b[i][j]-a[i][j]))             
#dp[h-1][w-1]
ans=10**10
for i in dp[h-1][w-1]:
    ans=min(ans,abs(i))
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
H,W=map(int,input().split())
a = [[] for _ in range(H)]
for i in range(H):
    a[i] = list(map(int, input().split()))
b = [[] for _ in range(H)]
for i in range(H):
    b[i] = list(map(int, input().split()))

for i in range(H):
    for j in range(W):
        a[i][j] =abs(a[i][j]-b[i][j])

dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0].add(a[0][0])
for i in range(1,H):
    t = a[i][0]
    tmp = set()
    for k in dp[i-1][0]:
        tmp.add(k+t)
        tmp.add(abs(k-t))
    dp[i][0] = tmp
for j in range(1,W):
    t = a[0][j]
    tmp = set()
    for k in dp[0][j-1]:
        tmp.add(k+t)
        tmp.add(abs(k-t))
    dp[0][j] = tmp
for i in range(1,H):
    for j in range(1,W):
        t = a[i][j]
        tmp = set()
        for k in (dp[i-1][j] | dp[i][j-1]):
            tmp.add(k+t)
            tmp.add(abs(k-t))
        dp[i][j] = tmp
        dp[i-1][j-1] = set()

ls = list(dp[H-1][W-1])
print(min(ls))
### BUGGY CODE ###

import sys
from collections import deque
def main():
    lines = sys.stdin.readlines()
    n, m = map(int, lines[0].split())
    cities={}
    mem_city = deque()
    for i in range(1, m+1):
        p, y = map(int, lines[i].split())
        mem_city.append((p, y))
        if p in cities:
            cities[p].append(y)
        else:
            cities[p] = [y]
    #print(cities)
    for key in cities:
        cities[key].sort()
    #print(cities)

    for p, y in mem_city:
        idx = cities[p].index(y) + 1
        print("{:06d}{:06d}".format(p, idx))
    return

main()

### FIXED CODE ###

import sys

def main():
    n, m = map(int, input().split())
    lines = sys.stdin.readlines()

    cities = {}
    for i in range(m):
        p, y = map(int, lines[i].split())
        if p in cities:
            cities[p].append((i, y))
        else:
            cities[p] = [(i, y)]

    outputs = [None] * m
    for pref, city_list in cities.items():
        city_list.sort(key=lambda x: x[1])
        #print(pref, city_list)
        city_no = 1
        for city in city_list:
            outputs[city[0]] = "{:06d}{:06d}".format(pref, city_no)
            city_no += 1

    for output in outputs:
        print(output)
    return


main()