Harryxun/stf_run huggingface dataset:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve():
    h, w, m = MAP()
    s = [LIST1() for i in range(m)]
    ay = [0]*h
    ax = [0]*w
    c = [[0]*w for i in range(h)]
    for x in s:
        ay[x[0]] += 1
        ax[x[1]] += 1
        c[x[0]][x[1]] = 1

    my = max(ay)
    mx = max(ax)
    
    by = bx = 0
    for y in ay:
        if y == my:
            by += 1
    for x in ax:
        if x == mx:
            bx += 1
            
    ans = my + mx
    tmp = 0
    for x in s:
        if ay[x[0]]+ax[x[1]]==ans:
            tmp += c[x[0]][x[1]]
    if tmp == by*bx:
        ans -= 1
    print(ans)
    
if __name__ == '__main__':
    solve()

### FIXED CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve():
    h, w, m = MAP()
    s = [LIST1() for i in range(m)]
    ay = [0]*h
    ax = [0]*w
    for x in s:
        ay[x[0]] += 1
        ax[x[1]] += 1

    my = max(ay)
    mx = max(ax)
    
    by = bx = 0
    for y in ay:
        if y == my:
            by += 1
    for x in ax:
        if x == mx:
            bx += 1
            
    ans = my + mx
    tmp = 0
    for x in s:
        if ay[x[0]]+ax[x[1]]==ans:
            tmp += 1
    if tmp == by*bx:
        ans -= 1
    print(ans)
    
if __name__ == '__main__':
    solve()
import copy

h, w = list(map(int, input().split()))
sharp = 0
D = []
for i in range(h):
    D.append(list(input()))
    # #の数を数えておく
    sharp += D[i].count('#')
ans = []
def dfs(row, column, count,data,ans):
    #もし配列の外を参照しているようであれば終了させる
    if(row > w - 1) or (column > h - 1) or ( row < 0 ) or ( column < 0 ):
        return

    if data[column][row] == '#':
        return
    #探索済みなので＃を入れたが、もっと良い方法があるかもしれない
    data[column][row] = '#'
    #その場所がゴールならば終了。ansにそこまでのコストを追加
    if column == h - 1 and row == w - 1:
        count += 1
        ans.append(count)
        return

    else:
        count += 1
        s = copy.deepcopy(data)
        ##dataの写しを引数として渡したい。参照渡しか値渡しかを確認
        #+-1ずつ四方向に全探索
        dfs(row + 1, column,     count, s,ans)
        dfs(row,     column + 1, count, s,ans)
        dfs(row - 1, column,     count, s,ans)
        dfs(row,     column - 1, count, s,ans)
        return

dfs(0, 0, 0,D,ans)
if len(ans) == 0:
    print(-1)
else:
    k = min(ans)
print(h * w - sharp - k)


### FIXED CODE ###

import collections
h, w = list(map(int, input().split()))
inf = h * w + 1
sharp = 0
data = []
for i in range(h):
    data.append(list(input()))
    # #の数を数えておく
    sharp += data[i].count('#')

ans = [[inf for i in range(w)] for j in range(h)]
def dfs(row, column, count,data):
    #もし配列の外を参照しているようであれば終了させる
    if(row > w - 1) or (column > h - 1) or ( row < 0 ) or ( column < 0 ):
        return

    if data[column][row] == '#':
        return
    data[column][row] == '#'
    #探索済みなので＃を入れたが、もっと良い方法があるかもしれない
    count += 1
    if row == w - 1 and column == h - 1:
        ans[column][row] = min(count, ans[column][row])
        return
    #その場所がゴールならば終了。ansにそこまでのコストを追加
    ##dataの写しを引数として渡したい。参照渡しか値渡しかを確認
    #+-1ずつ四方向に全探索
    dfs(row + 1, column,     count, data)
    dfs(row,     column + 1, count, data)
    dfs(row - 1, column,     count, data)
    dfs(row,     column - 1, count, data)
def bfs(row, column, count,data):
    becter = [-1,1]
    queue = collections.deque()
    queue.append([column, row,count])
    while len(queue) != 0:
        v = queue.popleft()
        if v[0] < 0 or v[1] < 0 or v[0] >= h or v[1] >= w:
            continue
        if data[v[0]][v[1]] != '#':

            data[v[0]][v[1]] = '#'
            v[2] += 1
            ans[v[0]][v[1]] = min(ans[v[0]][v[1]], v[2])
            queue.append([v[0] + 1, v[1],v[2]])
            queue.append([v[0], v[1] + 1,v[2]])
            queue.append([v[0] - 1, v[1],v[2]])
            queue.append([v[0], v[1] - 1,v[2]])


bfs(0, 0, 0,data)
if ans[-1][-1] == inf:
    print(-1)
    exit()
print(h * w - sharp - ans[-1][-1])
s = input().split(" ")
h = int(s[0])
w = int(s[1])
a = int(s[2])
b = int(s[3])

for i in range(b):
  for j in range(w):
  	if i < a:
    	print("1")
  	else:
      print("0")
    print("")

for i in range(h - b):
  for j in range(w):
    if i < a:
      print("0")
    else:
      print("1")
    print("")

### FIXED CODE ###

s = input().split(" ")
h = int(s[0])
w = int(s[1])
a = int(s[2])
b = int(s[3])

for i in range(b):
  for j in range(w):
    if j < a:
      print(1,end="")
    else:
      print(0,end="")
  print("")

for i in range(h - b):
  for j in range(w):
    if j < a:
      print(0,end="")
    else:
      print(1,end="")
  print("")
def main():
    from itertools import accumulate
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    sumA = sum(A)

    def enum_divisors(n):
        # 約数列挙
        divs = []
        for i in range(1, n+1):
            if i*i > n:
                break
            if n % i == 0:
                divs.append(i)
                if n//i != i:
                    # i が平方数でない
                    divs.append(n//i)
        return divs

    divs = enum_divisors(sumA)
    divs.sort(reverse=True)

    for d in divs:
        diff_n = []
        for a in A:
            diff_n.append(a % d)
        diff_n.sort()
        diff_p = []
        for dn in diff_n:
            diff_p.append(d - dn)
        S_n = list(accumulate([0] + diff_n))
        S_p = list(accumulate([0] + diff_p))
        if min(S_n[i] for i in range(1, N)
               if (S_n[i] - (S_p[N] - S_p[i])) == 0) <= K:
            print(d)
            return


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    sumA = sum(A)

    def trial_division(n):
        divs = []
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                divs.append(i)
                if i != n//i:
                    divs.append(n//i)
        return divs

    from itertools import accumulate
    divs = trial_division(sumA)
    ans = 0
    for d in divs:
        R = [a % d for a in A if a % d != 0]
        R.sort()
        S = [acc for acc in accumulate(R)]
        M = len(S)
        # print(d, R, S)
        if M == 0:
            ans = max(ans, d)
            continue
        for i in range(M-1):
            ne = S[i]
            po = d*(M-1-i) - (S[M-1] - S[i])
            if po == ne and po <= K:
                ans = max(ans, d)
    print(ans)


if __name__ == '__main__':
    main()
from math import pow
n = input()

MOD = 2019
ans = 0
dp = [0]*MOD
dp[0] = 1
temp = 0

for i in range(len(n)):
    temp = (temp+int(n[-i-1])*pow(10, i)) % MOD
    dp[temp] += 1

for item in dp:
    ans += item*(item-1)//2

print(ans)



### FIXED CODE ###

n = input()

MOD = 2019
ans = 0
dp = [0]*MOD
dp[0] = 1
temp = 0

for i in range(len(n)):
    temp = (temp+int(n[-i-1])*int(pow(10, i, MOD))) % MOD
    dp[temp] += 1

for item in dp:
    if item > 1:
        ans += item*(item-1)//2

print(ans)
while 1:
H , W = map(int, raw_input().split(" "))

if H == W == 0:
  break
width = ''
for _ in range(W):
  width += '#'
for _  in range(H):
  print width
    
    

### FIXED CODE ###

while 1:
  h, w = map(int, raw_input().split())
  if h == 0 and w == 0:
    break
  for i in range(h):
    print "#" * w
  print""
import scipy.misc as scm

h, w, a, b = [int(i) for i in input().split()]

p = 10 * * 9 + 7
s = 0

for i in range(w-b):
    s += scm.comb(h+w-a-2-i, w-1-i, 1) * scm.comb(a-1+i, a-1, 1)

print(s%p)


### FIXED CODE ###

import scipy.misc as scm

h, w, a, b = [int(i) for i in input().split()]

p = 10**9 + 7
ans = 0

def fact(n, p=10**9 + 7):
    f = [1]
    for i in range(1, n+1):
        f.append(f[-1]*i%p)
    return f

def invfact(n, f, p=10**9 + 7):
    inv = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        inv.append(inv[-1]*i%p)
    return inv[::-1]

f = fact(h+w)
rf = invfact(h+w, f)

for i in range(w-b):
    wi = b + i
    ans += (f[h-a+wi-1] * rf[h-a-1] % p * rf[wi] % p) * (f[a+w-wi-2] * rf[a-1] % p * rf[w-wi-1] % p) % p
    ans %= p 

print(ans)
import scipy
def main():


    print(13)

main()

### FIXED CODE ###

def main():
    [N,W]=input().split(" ")
    N=int(N)
    W=int(W)
    inputset=[]
    for i in range(N):
        [vi,wi]=input().split(" ")
        inputset.append([int(vi),int(wi)])

    graph=[]
    for i in range(N+1):
        graph.append([])
        for j in range(W+1):
            graph[i].append(0)

    for i in range(N):
        for j in range(W+1):
            if(inputset[i][1]>j):
                graph[i+1][j]=graph[i][j]
            else:
                rest=j-inputset[i][1]
                choosevalue=graph[i][rest]+inputset[i][0]
                nonchoosevalue=graph[i][j]
                if(choosevalue>nonchoosevalue):
                    graph[i+1][j]=choosevalue
                else:
                    graph[i+1][j]=nonchoosevalue

    print(graph[N][W])

main()
#AGC030 B - Powers of two
beki=[]
for i in range(1,32):
    beki.append(2**i)#bekiは２のべき乗の配列
N=int(input())
for i in range(N):
    A[i]=int(A[i])
sorted(A)#Aを昇順にソート
for i in (reversed(beki)):
    inverseA=[]
    for j in range(len(A)):
        inverseA.append(i-A[j])#inverseA
    for j in range(len(A)):
        if inverseA[j] in A:
            A.remove(inverseA[j])
print((N-len(A))%2)

### FIXED CODE ###

#AGC029 A - Irreversible operation
def countB(data):#dataのBの個数kosuとiの総和sumを返す
    sum=0
    kosu=0
    for i in range(len(data)):
        if data[i]=="B":
            kosu=kosu+1
            sum=sum+i
    return[sum,kosu]

text=input()
S=[]
N=len(text)
for i in range(N):
    S.append(text[i])
result=countB(S)
x=result[1]
Ans=int((2*N-x-1)*x/2-result[0])
print(Ans)
l=input()
n=(len(l)+1)//2
for i in range(n):
  odd+=l[2*i]
print(odd)

### FIXED CODE ###

l=input()
n=(len(l)+1)//2
odd=""
for i in range(n):
  odd+=l[2*i]
print(odd)
S=input()
flag=False
for i in range(len(S)):
  if i%2==0:
    if S[i]!='R' and S[i]!='U' and S[i]!='D':
      flag=True
  else:
    if S[i]!='L' and S[i]!='U' and S[i]!='D':
      flag=True
if flag=True:
  print('No')
else:
  print('Yes')

### FIXED CODE ###

S=input()
flag=False
for i in range(len(S)):
  if i%2==0:
    if S[i]!='R' and S[i]!='U' and S[i]!='D':
      flag=True
  else:
    if S[i]!='L' and S[i]!='U' and S[i]!='D':
      flag=True
if flag==True:
  print('No')
else:
  print('Yes')
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def calc(n, k):
    if n == 0:
        ans=0
    else:
        ans = 0
        digits = int(math.log10(n))+1
        #Nより小さい桁数
        if k <= digits-1:
            for n_dig in range(k, digits):
                ans += 9 * combinations_count(n_dig-1,k-1) * (9**(k-1))
                #print(n_dig,tot)
        #Nと桁数が同じ
        top = n//10**(digits-1)
        ans += (top-1) * combinations_count(digits-1,k-1) * (9**(k-1))
        if k>1:
            ans += calc(n-top*10**(digits-1), k-1)
        elif k==1:
            ans += 1
    #print(n,k,ans)
    return ans
    

N = int(input())
K = int(input())

tot = calc(N,K)

print(tot)
    


### FIXED CODE ###

import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def calc(n, k):
    if n < 10**(k-1):
        ans = 0
    elif n == 0:
        ans=0
    else:
        ans = 0
        digits = int(math.log10(n))+1
        #Nより小さい桁数
        if k <= digits-1:
            for n_dig in range(k, digits):
                ans += 9 * combinations_count(n_dig-1,k-1) * (9**(k-1))
                #print(n_dig,tot)
        #Nと桁数が同じ
        top = n//10**(digits-1)
        ans += (top-1) * combinations_count(digits-1,k-1) * (9**(k-1))
        if k>1:
            ans += calc(n-top*10**(digits-1), k-1)
        elif k==1:
            ans += 1
    #print(n,k,ans)
    return ans
    

N = int(input())
K = int(input())

tot = calc(N,K)

print(tot)
a, b = map(int, input().split())

if((a*b) % 2 == 0){
  print('Even')
} else {
  print('Odd')
}


### FIXED CODE ###

a, b = map(int, input().split())

if (a*b) % 2 == 0:
  print('Even')
else:
  print('Odd')
base = {'A':'A', 'C':'T', 'G':'C', 'T':'G'}

b = int(input())
print(base[b])


### FIXED CODE ###

base = {'A':'T', 'C':'G', 'G':'C', 'T':'A'}
 
b = input()
print(base[b])
n = int(input())

before = ["1"]
for i in range(n-1):
    next = []
    for elem in before:
        m = 1
        for j in range(len(elem)):
            m = max(m, int(elem[j]))
        for j in range(m+1):
            next.append(elem+str(j+1))
    before = next[:]

before.sort()
d = {"1":"a", "2":"b", "3":"c", "4":"d", "5":"e", "6":"f", "7":"g", "8":"h", "9":"i", "10":"j"}
for elem in before:
    ans = []
    for i in range(len(elem)):
        ans.append(d[elem[i]])
    print("".join(ans))


### FIXED CODE ###

n = int(input())

before = ["0"]
for i in range(n-1):
    next = []
    for elem in before:
        m = 1
        for j in range(len(elem)):
            m = max(m, int(elem[j])+1)
        for j in range(m+1):
            next.append(elem+str(j))
    before = next[:]

before.sort()
d = {"0":"a", "1":"b", "2":"c", "3":"d", "4":"e", "5":"f", "6":"g", "7":"h", "8":"i", "9":"j"}
for elem in before:
    ans = []
    for i in range(len(elem)):
        ans.append(d[elem[i]])
    print("".join(ans))
while True: 
	h , w=map(int, input().split())
	if (h==0) and (w==0): 
                break
        else:
		print('#'*w)
		for I in  range(h-2):
		print('#'+'.'*(w-2)+'#')
		print('#'*w)
 


### FIXED CODE ###

while 1:
        (H,W)=[int(i) for i in input().split()]
        if H==W==0:
                break
        print('#'*W)
        for i in range(H-2):
                print('#'+'.'*(W-2)+'#')
        print('#'*W)
        print('')
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N,K=map(int,input().split())

for i in range(1,K+1):
    x=combinations_count(K-1,i-1)
    y=combinations_count(N-K+1,i)
    print((x*y)%1000000007)




### FIXED CODE ###

import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N,K=map(int,input().split())

for i in range(1,K+1):
    x=combinations_count(K-1,i-1)
    if N-K+1>=i:
        y=combinations_count(N-K+1,i)
        print((x*y)%1000000007)
    else:
        print(0)
#distance
import math
x1,y1,x2,y2=map(int,input().split())
distance = math.sqrt((x2-x1)**2+(y2-y1)**2)
print(distance)

### FIXED CODE ###

#distance
import math
x1,y1,x2,y2=map(float,input().split())
distance = math.sqrt((x2-x1)**2+(y2-y1)**2)
print(distance)
# -*- coding: utf-8 -*-
import itertools


def filter_name(n):
    return n.startswith("M") or n.startswith("A") or n.startswith("R") or n.startswith("C") or n.startswith("H")


def filter_ok(l):
    dic = {'M': 0, 'A': 0, 'R': 0, 'C': 0, 'H': 0}
    for i in l:
        dic[i[0:1]] += 1
    for num in dic.values():
        if num >= 2:
            return False
    return True


n = input()
a = []
for i in range(n):
    a.append(raw_input())

r = filter(filter_name, a)
c = list(itertools.combinations(r, 3))
r = filter(filter_ok, c)
print len(r)


### FIXED CODE ###

# -*- coding: utf-8 -*-
a = int(raw_input())
print (a/3)
for s in range(n):
    s = str(s[k])
    s = s.lower()

print(s)


### FIXED CODE ###

N, K = (int(i) for i in input().split())
S = list(input())

S[K - 1] = S[K - 1].lower()
print(''.join(S))
n, k = map(int, input().split())
list1, list2, k = [], [], k*2
for x in range(k):
    list1.append(input().split())
while i < k:
    for j in list1[i]:
        list2.append(j)
    i += 2
print(n - len(set(list2)))


### FIXED CODE ###

n, k = map(int, input().split())
li = []
for x in range(k*2):
    li.append(input().split())
li2 = []
i = 1
while i < k*2:
    for j in li[i]:
        li2.append(j)
    i += 2
li2 = set(li2)
print(n - len(li2))
a = int(input())
b = int(input())

if a <= 8 and b <= 8:
    print("Yay!")
else:
    print(":()")

### FIXED CODE ###

a,b = map(int,input().split())

if a <= 8 and b <= 8:
    print("Yay!")
else:
    print(":(")
from sys import stdin
import bisect

n,m = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(m)]

lin = [[]for i in range(n)]
lin2 = []
li3 = []
for j in range(m):
    lin[li[j][0]-1].append(li[j][1])
    lin2.append(li[j][0]-1)

for j in range(n):
    liv = sorted(lin[j])
    li3.append(liv)

for k in range(m):
    s = len(str(li[k][1]))
    v = len(str(li[j][0]))
    print("0"*(6-v)+str(li[k][0])+"0"*(6-s)+str(bisect.bisect(li3[li[k][0]-1],li[k][1])))

### FIXED CODE ###

from sys import stdin
import bisect

n,m = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(m)]

lin = [[]for i in range(n)]
lin2 = []
li3 = []
for j in range(m):
    lin[li[j][0]-1].append(li[j][1])
    lin2.append(li[j][0]-1)

for j in range(n):
    liv = sorted(lin[j])
    li3.append(liv)

for k in range(m):
    tosi = str(li[k][0]).zfill(6)
    ban =  str(bisect.bisect(li3[li[k][0]-1],li[k][1])).zfill(6)
    print(tosi+ban)
N,M = map(int,input().split())
ks = []
for i in range(M):
  ks.append(list(map(int,input().split())))
p = list(map(int, input().split()))
c = 0

for i in range(2 ** N):
  sw = [0]*N
  for j in range(N):
    if ((i >> j) & 1):
      sw[j] = 1
  frg = True
  for j in range(M):
    a = ks[j][0]
    aa = 0
    for k in range(a):
      aa += sw[k+1]
    if aa%2 != p[j]:
      frg = False
  if frg:
    c += 1
    
print(c)

### FIXED CODE ###

N,M = map(int,input().split())
ks = []
for i in range(M):
  ks.append(list(map(int,input().split())))
p = list(map(int, input().split()))
c = 0

for i in range(2 ** N):
  sw = [0]*N
  for j in range(N):
    if ((i >> j) & 1):
      sw[j] = 1
  frg = True
  for j in range(M):
    a = ks[j][0]
    aa = 0
    for k in range(1,a+1):
      aa += sw[ks[j][k]-1]
    if aa%2 != p[j]:
      frg = False
  if frg:
    c += 1
    
print(c)
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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



N, M =two_int()

key_list=[]
treasures=[]

for i in range(M):
    mon,_ =two_int()
    key_list.append(mon)
    
    temp=[0 for i in range(N)]
    for j in many_int():
        temp[N-j-1]=1
    treasures.append("0b"+"".join(list(map(str,temp))))

max_index=2**N
INF=10**15

dp=[INF for i in range(max_index)]
dp[0]=0

for i in range(max_index):
    for j in range(M):
        new_i = int(bin(treasures[j] | i),2)
        cost = dp[i] + key_list[j]
        dp[new_i] = min(dp[new_i], cost) 

goal_index=max_index-1
if dp[goal_index]!=INF:
    print(dp[goal_index])
else:
    print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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


def main():
    N, M =two_int()

    key_list=[]
    treasures=[]
    check={}

    for i in range(M):
        mon,_ =two_int()
        temp = map(lambda x: 1<<(x-1), many_int())
        sums = sum(temp)
        
        if sums in check:
            if check[sums] > mon:
                check[sums]=mon
        else:
            check[sums]=mon
            
    for k,v in check.items():
        key_list.append(v)
        treasures.append(k)

    max_index=2**N
    INF=10**15

    dp=[INF for i in range(max_index)]
    dp[0]=0
    M=len(key_list)

    for i in range(max_index-1):
        for j in range(M):
            new_i = int(bin(treasures[j] | i),2)
            cost = dp[i] + key_list[j]
            dp[new_i] = min(dp[new_i], cost) 
        
    goal_index=max_index-1
    if dp[goal_index]!=INF:
        print(dp[goal_index])
    else:
        print(-1)

main()
n,m = map(int,input().split( ))
ls_a = []
ls_b = [[] for i in range(n)]
for i in range(m):
    p,y = map(int,input().split( ))
    ls_a.append([p,y])
    ls_b[p-1].append(y)
for i in range(n):
    if len(b[i]) !=0:
        ls_b[i].sort()
for i in range(m):
    print(str(ls_a[i][0]).zfill(6) + str(ls_b[ls_a[i][0]-1].index(ls_a[i][1])+1).zfill(6))

### FIXED CODE ###

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])
if x == 1:
	print(0)
else:
	print(1)

### FIXED CODE ###

if int(input()) == 0:
	print(1)
else:
	print(0)
a = input()
b = input()
b.pop()
if a == b[:-1]:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

a = input()
b = input()
if a == b[:-1]:
  print('Yes')
else:
  print('No')