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

N, K = map(int, input().split())
P = list(map(lambda s: int(s) - 1, input().split()))
C = list(map(int, input().split()))

ans = -1_000_000_000
for i in range(N):
    S = [C[i]]
    p = P[i]
    while p != i:
        S.append(C[p])
        p = P[p]
    s = sum(S)
    n = len(S)
    acc = 0
    for i in range(min(n, K + 2)):
        acc += S[i]
        a = acc
        if s > 0:
            a += s * ((K - (i + 1)) // n)
        ans = max(a, ans)

print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(lambda s: int(s) - 1, input().split()))
C = list(map(int, input().split()))

ans = -1_000_000_000
for i in range(N):
    S = [C[i]]
    p = P[i]
    while p != i:
        S.append(C[p])
        p = P[p]
    s = sum(S)
    n = len(S)
    acc = 0
    for i in range(min(n, K + 2)):
        acc += S[i]
        a = acc
        if s > 0:
            a += s * ((K - (i + 1)) // n)
        ans = max(a, ans)

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

#atcoder_RedAndBlueBalls

import numpy as np 

MAX = pow(10,9)+7
def fact(n):
    acc = 1 
    for i in range(n):
        acc*=i+1 
    return acc

def C(n,m):
    return (fact(n)//(fact(m)*fact(n-m))) 

n,k = input().split()
n,k = int(n),int(k) 

for i in range(k):
    ans = (C(n-k+1,i+1) * C(k-1,i) ) % MAX 
    print (ans)



### FIXED CODE ###

#atcoder_RedAndBlueBalls

import numpy as np 

MAX = pow(10,9)+7

def fact(n):
    ls = [1] 
    for i in range(1,n+1):
        ls.append(ls[i-1]*i) 
    return(ls) 

n,k = input().split()
n,k = int(n),int(k) 

ls = fact(2000)

def C(n,m):
    return ((ls[n]//(ls[m]*ls[n-m])) % MAX)

for i in range(k):
    ans = ( C(n-k+1,i+1) * C(k-1,i) ) % MAX 
    print (ans)
### BUGGY CODE ###

n = int(input())
p = sorted(list(map(int, input().split())))
mid = n // 2
ans = 0
for i in range(p[mid-1], p[mid]):
  if len([j for j in p if j > i]) == mid:
    ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
p = sorted(list(map(int, input().split())))
mid = n // 2
print(p[mid] - p[mid-1])
### BUGGY CODE ###

A,B,M=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=[list(map(int,input().split())) for i in range(M)]
d = 0
e = 10**10

for i in range(A):
	for j in range(B):
		d = a[i]+b[j]
		if d<e:
			e=d

for i in range(M):
	d=a[c[i][0]-1]+b[c[i][1]-1]-c[i][2]
	if d<e:
		e=d

print(e)

### FIXED CODE ###

A,B,M=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=[list(map(int,input().split())) for i in range(M)]
d = 0
e = 0
aa=sorted(a)
bb=sorted(b)

e=aa[0]+bb[0]

for i in range(M):
	d=a[c[i][0]-1]+b[c[i][1]-1]-c[i][2]
	if d<e:
		e=d

print(e)
### BUGGY CODE ###

def main(N, K, h):
    dp = [float('INF')] * N
    dp[0] = 0
    for i in range(N):
        for j in range(1,K+1):
            if i+j <= N-1:
                dp[i+j] = min(dp[i+j], dp[i] + (abs(h[i+j] - h[i])))
    return dp[-1]

N,K = map(int, input().split())
h = list(map(int,input().split()))
print(main(N, K, h))

### FIXED CODE ###

def main(N, K, h):
    dp = [float('INF')] * N
    dp[0] = 0
    for i in range(N):
        for j in range(1,K+1):
            if i+j <= N-1:
                dp[i+j] = min(dp[i+j], dp[i] + (abs(h[i+j] - h[i])))
    return dp[-1]

N,K = map(int, input().split())
h = list(map(int,input().split()))
print(main(N, K, h))
### BUGGY CODE ###

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

for i in range(N-1):
    Ans = 0
    for j in range(N-1):
        if i+1 == A[j]:
            Ans += 1
    print(Ans)
print("0")

### FIXED CODE ###

#200419C
N = int(input())
A = list(map(int,input().split()))
A = sorted(A)

count = 0
for i in range(N-1):
    L = len(A)
    #print(A)
    Ans = 0
    count += Ans
    for j in range(L-count):
        if A[count + j]==i+1:
            Ans += 1
        else:            
            break
    print(Ans)
    count += Ans

        
print("0")
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Feb 26 17:52:43 2019

@author: nakamuratakayuki
"""

R,G,B,N = tuple(map(int,input().split()))
L = [R,G,B]
L.sort(reverse=True)
c = 0
rmax = N//L[0]

for i in range(rmax+1):
    gmax = (N-L[0]*i)//L[1]
    for j in range(gmax+1):
        bmax = (N-L[0]*i-L[1]*j)//L[2]
        for k in range(bmax+1):
            if L[0]*i+L[1]*j+L[2]*k == N:
                c += 1

print(c)

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Feb 26 17:52:43 2019

@author: nakamuratakayuki
"""

R,G,B,N = tuple(map(int,input().split()))
L = [R,G,B]
L.sort(reverse=True)
c = 0
rmax = N//L[0]

for i in range(rmax+1):
    Nc = N
    Nc -= i*L[0]
    if Nc%L[2] == 0:
            c += 1
    while True:
        Nc -= L[1]
        if Nc < 0:
            break
        if Nc%L[2] == 0:
            c += 1

print(c)
### BUGGY CODE ###

N =int(input())
s = list(sorted(input()) for i in range(N))
cnt = 0
for i in range(N):
    for j in range(i+1,N):
        if s[i]==s[j]:
            cnt+=1
print(cnt)

### FIXED CODE ###

import collections

N =int(input())
s = ["".join(sorted(input())) for _ in range(N)]
c = collections.Counter(s)
cnt = 0
ans =0
for i in set(s):
    cnt = c[i]
    ans += cnt*(cnt-1)//2
print(ans)
### BUGGY CODE ###

import sys

def main():
    input=sys.stdin.readline
    n,q=map(int,input().split())

    edge=[[] for _ in range(n)]
    for _ in range(n-1):
        u,v=map(int,input().split())
        u-=1;v-=1
        edge[u].append(v)

    res=[0]*n

    def solve(p,x):
        que=[p]
        while que:
            p=que.pop()
            res[p]+=x
            for e in edge[p]:
                que.append(e)
        return
    
    px={}
    for _ in range(q):
        p,x=map(int,input().split())
        p-=1
        px[p]=px.get(p,0)+x

    for p,x in px.items():
        solve(p,x)

    print(*res)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from collections import deque
def main():
    input=sys.stdin.readline
    n,q=map(int,input().split())

    edge=[[] for _ in range(n)]
    for _ in range(n-1):
        u,v=map(int,input().split())
        u-=1;v-=1
        edge[u].append(v)
   
    cost=[0]*n
    for _ in range(q):
        p,x=map(int,input().split())
        p-=1
        cost[p]+=x

    for idx,e in enumerate(cost):
        if e==0:continue
        for f in edge[idx]:
            cost[f]+=e

    print(*cost)

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

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

r = [max(a[0:i]+a[i+1:]) for i in range(n)]

for answer in r:
     print(answer)

### FIXED CODE ###

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

a_max = max(a)
idx = [i for i, x in enumerate(a) if x==a_max]

if len(idx) > 1:
    for i in range(n):
        print(a_max)
else:
    for i in range(n):
        if a[i] == a_max:
            print(max(a[0:i]+a[i+1:]))
        else:
            print(a_max)
### BUGGY CODE ###

import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
import numpy as np

h,w,k = na()
s = []
for i in range(h):
    o = list(np.cumsum(list(map(int, list(ns())))))
    s.append(o)

s = np.array(s)

ans = 1000000000000000000



for i in range(2**(h-1)):
    b = np.array([0]*w)
    c = []
    d = 0 #分割数
    for j in range(h):
        b += np.array(s[j])
        if j == h:
            break
        if ((i >> j) & 1):
            c.append(list(b))
            b = np.array([0]*w)
            d += 1
    c.append(list(b))
    e = -1
    for p in range(w):
        flag = False
        for l in c:
            u = 0 if e == -1 else l[e]
            if l[p]-u > k:
                if p-e == 1:
                    flag = True
                    break
                e = p-1
                d += 1
                break
        if flag:
            d = 1000000000000000000
            break
    ans = min(ans, d)

print(ans)

### FIXED CODE ###

import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

h,w,k = na()
s = []
for i in range(h):
    o = list(map(int, list(ns())))
    q = 0
    r = []
    for x in o:
        q += x
        r.append(q)
    s.append(r)

ans = 1000000000000000000

for i in range(2**(h-1)):
    b = [0]*w
    c = []
    d = 0 #分割数
    for j in range(h):
        b = [x + y for (x, y) in zip(b, s[j])]
        if j == h:
            break
        if ((i >> j) & 1):
            c.append(b)
            b = [0]*w
            d += 1
    c.append(b)
    e = -1
    for p in range(w):
        flag = False
        for l in c:
            u = 0 if e == -1 else l[e]
            if l[p]-u > k:
                if p-e == 1:
                    flag = True
                    break
                e = p-1
                d += 1
                break
        if flag:
            d = 1000000000000000000
            break
    ans = min(ans, d)

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

N = int(input())
S = input()

answer = float('inf')
for i in range(N):
    lcount = 0 if i == 0 else S[:i].count('W')
    rcount = 0 if i == N-1 else S[i:].count('E')
    answer = min(answer, lcount+rcount)

print(answer)

### FIXED CODE ###

N = int(input())
S = input()

answer = prev = S[1:].count('E')
for i in range(1, N):
    _answer = prev if S[i-1] == 'E' else prev+1
    if S[i] == 'E':
        _answer -= 1
    answer = min(answer, _answer)
    prev = _answer

print(answer)
### BUGGY CODE ###

t = list(input())
count = 0
nums = []
num = []
ans = []
 
for i in range(len(t)):
  if t[i] == '?':
    count += 1
    num.append(i)
 
for j in range(2**count):
  tmp = ['D'] * count
  for k in range(count):
    if j >> k & 1:
      tmp[k] = 'P'
    a = num[k]
    t[a] = tmp[k]
  b = ''.join(t)
  nums.append(b)
  c = int(b.count('PD')) + int(b.count('D'))
  ans.append(c)
  
d = ans.index(max(ans))
print(nums[d])

### FIXED CODE ###

t = list(input())
t = ''.join(t)
t = t.replace('?',  'D')

print(t)
### BUGGY CODE ###

a = input()
b = input()
c = input()

def align(s1, s2):
    l1 = len(s1)
    l2 = len(s2)
    res = [s1 + s2]
    for i in range(l1):
        f = 0
        for j in range(min(l2, l1-i)):
            if s1[i+j] != s2[j] and s1[i+j] != '?' and s2[j] != '?':
                f = 0
                break
            else:
                f = 1
        if f:
            res.append(s1 + s2[j+1:])
    res.sort(key = lambda x:len(x))
    return res

cand = [[a, b, c], [a, c, b], [b, a, c], [b, c, a], [c, a, b], [c, b, a]]

res = 6000

for l in cand:
    tmp = align(l[0], l[1])
    for item in tmp:
        ans = align(item, l[2])
        res = min(res, len(ans[0]))

print(res)


### FIXED CODE ###

a = input()
b = input()
c = input()

def match(c1, c2):
    return c1 == '?' or c2 == '?' or c1 == c2

M = 2000

ab, ac, bc = [], [], []
ab_append = ab.append
ac_append = ac.append
bc_append = bc.append

for _  in range(10000):
    ab_append(0)
    ac_append(0)
    bc_append(0)

for _  in range(10000):
    bc_append(0)

A, B, C = len(a), len(b), len(c)
for i in range(A):
    for j in range(B):
        if not match(a[i], b[j]):
            ab[i-j+5000] = 1
for i in range(A):
    for j in range(C):
        if not match(a[i], c[j]):
            ac[i-j+5000] = 1
for i in range(B):
    for j in range(C):
        if not match(b[i], c[j]):
            bc[i-j+10000] = 1

ans = 3 * M

for i in range(-2*M, 2*M):
    for j in range(-2*M, 2* M):
        if ab[i+5000] == 0 and ac[j+5000] == 0 and bc[j-i+10000] == 0:
            L = min(0, min(i, j))
            R = max(A, max(B+i, C+j))
            ans = min(ans, R - L)

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

H,W=map(int,input().split())
S=[]
for i in range(H):
  S.append(input())
  
L=[[0 for i in range(W)] for j in range(H)]
R=[[0 for i in range(W)] for j in range(H)]
D=[[0 for i in range(W)] for j in range(H)]
U=[[0 for i in range(W)] for j in range(H)]
A=[[0 for i in range(W)] for j in range(H)]

for i in range(H):
  for j in range(W):
      if S[i][j]=='.':
        L[i][j]=L[i][j-1]+1 if j!=0 else 1
      else:
        L[i][j]=0
#print(L)

for i in range(H):
  for j in reversed(range(W)):
      if S[i][j]=='.':
        R[i][j]=R[i][j+1]+1 if j!=W-1 else 1
      else:
        R[i][j]=0
#print(R)

for j in range(W):
  for i in range(H):
      if S[i][j]=='.':
        U[i][j]=U[i-1][j]+1 if i!=0 else 1
      else:
        U[i][j]=0
#print(U)

for j in range(W):
  for i in reversed(range(H)):
      if S[i][j]=='.':
        D[i][j]=D[i+1][j]+1 if i!=H-1 else 1
      else:
        D[i][j]=0
#print(D)

for i in range(H):
  for j in range(W):
    A[i][j]=L[i][j]+R[i][j]+D[i][j]+U[i][j]-3

res = -1
for i in range(H):
  res = max(res,max(A[i]))
print(res)

### FIXED CODE ###

import numpy as np

H,W=map(int,input().split())
S=np.array([list(input()) for _ in range(H)])=='.'
D=np.zeros((H,W),dtype=int)
U=np.zeros((H,W),dtype=int)
L=np.zeros((H,W),dtype=int)
R=np.zeros((H,W),dtype=int)

for i in range(H):
  U[i]=(U[i-1]+1)*S[i]
  D[-i-1]=(D[-i]+1)*S[-i-1]
for i in range(W):
  L[:,i]=(L[:,i-1]+1)*S[:,i]
  R[:,-i-1]=(R[:,-i]+1)*S[:,-i-1]
#print(L)
print(np.max(U+D+L+R)-3)
### BUGGY CODE ###

s = [input() for i in range(2)] 
li = list(map(int, s[1].split()))
s0 = int(s[0])
f1 = 1
for i in range(s0):
    f1 = f1 * li[i]
if f1 > 1000000000000000000:
    print(-1)
if f1 <= 1000000000000000000:
    print(f1)

### FIXED CODE ###

s = [input() for i in range(2)] 
li = list(map(int, s[1].split()))
s0 = int(s[0])
f1 = 1
if 0 in li:
    print(0)
if 0 not in li:
    for i in range(s0):
        f1 = f1 * li[i]
        if f1 > 1000000000000000000:
            print(-1)
            break
    if f1 <= 1000000000000000000:
        print(f1)
### BUGGY CODE ###

import sys
from itertools import combinations
read = sys.stdin.read

N, K, *xy = map(int, read().split())
xy = list(zip(*[iter(xy)] * 2))
X = [x for x, y in xy]
Y = [y for x, y in xy]
answer = 10 ** 20

for i in combinations(X, 2):
    for j in combinations(Y, 2):
        top = max(j)
        bottom = min(j)
        left = min(i)
        right = max(i)
        cnt = 0
        for x, y in xy:
            if left <= x <= right and bottom <= y <= top:
                cnt += 1
        if cnt < K:
            continue

        S = (top - bottom) * (right - left)
        if S < answer:
            answer = S

print(answer)

### FIXED CODE ###

import sys
from itertools import combinations
read = sys.stdin.read

N, K, *xy = map(int, read().split())
xy = sorted(zip(*[iter(xy)] * 2))
X, Y = zip(*xy)
answer = 10 ** 20

for left, right in combinations(range(N), 2):
    width = X[right] - X[left]
    tmp_Y = sorted(Y[left:right + 1])
    h = len(tmp_Y)
    for i in range(h):
        if i + K > h:
            break

        S = width * (tmp_Y[i + K - 1] - tmp_Y[i])
        if S < answer:
            answer = S

print(answer)
### BUGGY CODE ###

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    ans = []
    ans_append = ans.append
    for i in range(n):
        ans_append(a.index(i + 1) + 1)
    print(*ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys


def main():
    n = int(input())
    a = [int(i) for i in sys.stdin.readline().split()]
    ans = [0] * n
    for i in range(n):
        ans[a[i] - 1] = i + 1
    print(*ans)


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

N=int(input())
a=[int(input()) for i in range(N) ]
a_M=[]
for i in range(N):
    s=a[i]
    a[i]=0
    a_M.append( max(a) )
    a[i]=s
for x in a_M:
    print(x)

### FIXED CODE ###

#134
N=int(input())
a=[int(input()) for i in range(N) ]
a_M=[]
a_M1=sorted(a)[-1]
a_M2=sorted(a)[-2]
for i in range(N):
    if a[i]==a_M1:
        a_M.append(a_M2)
    else:
        a_M.append(a_M1)
for x in a_M:
    print(x)
### BUGGY CODE ###

H = int(input())

count = 0
number = 1
while True:
    H = H // 2
    number *= 2
    if H == 1:
        count += number + 1
        break
    else:
        count += number

print(count)

### FIXED CODE ###

H = int(input())
import numpy as np
from math import ceil

L = int(np.log2(H))
K = ceil(np.log2(H))
if K == L:
    count = K
else:
    count = K - 1
L = 2 ** (count + 1) - 1

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

n = int(input())

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

print(max(a[1:]))

for i in range(1, n-1):

  print(max(max(a[:i]), max(a[i+1:])))

print(max(a[:-1]))
  
  

### FIXED CODE ###

n = int(input())

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

a_max = max(a)
a_max_count = a.count(a_max)

if a_max_count > 1:
  for i in range(n):
    print(a_max)
    
else:
  print(max(a[1:]))
  
  for i in range(1, n-1):
    if a[i] == a_max:
      print(max(max(a[:i]), max(a[i+1:])))
      
    else:
      print(a_max)

  print(max(a[:-1]))
### BUGGY CODE ###

import numpy as np
N, K = list(map(int, input().split()))
A = np.array(list(map(int, input().split()))) - 1
mem = np.zeros((N, 2))

c = 0 # 現在の場所
cK = 0 # 現在の回数
flg = True
mem[c] += 1
mem[c][1] = 0
for k in range(1, K+1):
    c = A[c] # k回目の移動先
    mem[c][0] += 1
    if np.any(mem.T[0]>1):
        T = k - mem[c][1]
        cK = k
        flg = False
        break
    mem[c][1] = k

if flg:
    print(c+1)
else:
    iterN = int(np.mod(int(K - cK), int(T)))
    for i in range(iterN):
        c = A[c]
    print(c+1)

### FIXED CODE ###

import numpy as np
N, K = list(map(int, input().split()))
A = np.array(list(map(int, input().split()))) - 1
mem = {}

c = 0 # 現在の場所
cK = 0 # 現在の回数
flg = True
mem[c] = 0
for k in range(1, K+1):
    c = A[c] # k回目の移動先
    if c in mem:
        T = k - mem[c]
        cK = k
        flg = False
        break
    mem[c] = k

if flg:
    print(c+1)
else:
    iterN = int(np.mod(int(K - cK), int(T)))
    for i in range(iterN):
        c = A[c]
    print(c+1)
### BUGGY CODE ###

n = int(input())
import numpy as np
arr = np.array(list(set(map(int, input().split()))))

from collections import deque
q = deque([arr])
ans = arr.min()
while len(q) > 0:
    ar = q.popleft()
    ans = min(ar.min(), ans)
    if ans == 1:
        break
    for mon in ar:
        tmp = (ar - 1) % mon + 1
        if np.any(ar != tmp):
            q.append(np.array(list(set(tmp))))

print(ans)


### FIXED CODE ###

n = int(input())
from functools import reduce
from fractions import gcd
ans = reduce(gcd, (map(int, input().split())))

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

N,K = map(int,input().split())
h = [int(i) for i in input().split()]

def chmin(a,b):
    if a > b:
        return b
    else:
        return a

dp = [float("inf") for _ in range(N)]
dp[0] = 0

for i in range(N-1):
    for k in range(1,chmin(K+1,N-i)):
        dp[i+k] = chmin(dp[i+k],dp[i]+abs(h[i]-h[i+k]))

print(dp[N-1])

### FIXED CODE ###

N,K = map(int,input().split())
h = [int(i) for i in input().split()]

def chmin(a,b):
    if a > b:
        return b
    else:
        return a

dp = [float("inf") for _ in range(N)]
dp[0] = 0

for i in range(N-1):
    for k in range(1,chmin(K+1,N-i)):
        dp[i+k] = chmin(dp[i+k],dp[i]+abs(h[i]-h[i+k]))

print(dp[N-1])
### BUGGY CODE ###

#A,B,C=(int(x) for x in input().split())
N=int(input())
A=list(map(int, input().split()))

t=A[0]
i=1
for k in range(N-1):
  t=t*A[i]
  i+=1
if t<=10**18:
  print(t)
else:
  print(-1)

### FIXED CODE ###

#A,B,C=(int(x) for x in input().split())
N=int(input())
A=list(map(int, input().split()))


if 0 in A:
  t=0
else:
  t=A[0]
  i=1
  for k in range(N-1):
    t=t*A[i]
    if t>10**18:
      break
    i+=1

if t<=10**18:
  print(t)
else:
  print(-1)
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

result = []
for i in range(len(A)):
    for j in range(len(B)):
        for k in range(len(C)):
            result.append(A[i]+B[j]+C[k])

result.sort(reverse=True)

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


### FIXED CODE ###

x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
e=[]
for ai in a:
    for bi in b:
        e.append(ai+bi)
e.sort(reverse=True)
e=e[:k]
ans=[]
for ci in c:
    for ei in e:
        ans.append(ci+ei)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

a, b, n = map(int, input().split())
ans = 0
m = 10000
for x in range(1,n+1):
    f = b - x % b
    if m > f:
        m = f
        ans =  x/b -x//b
print(int(ans*a))

### FIXED CODE ###

a, b, n = map(int, input().split())
M = min(b-1,n)
print(int((M/b-M//b) * a))
### BUGGY CODE ###

n,m = map(int,input().split())
py = []
for i in range(m):
    p,y = map(int,input().split())
    py.append([p,y])
spy = sorted(py,key=lambda x:x[1])

cnt = [0]*n
id = []
for i in spy:
    p,y = i
    cnt[p-1] += 1
    id.append(str(p).zfill(6)+str(cnt[p-1]).zfill(6))

for i in py:
    index = spy.index(i)
    print(id[index])

### FIXED CODE ###

from collections import defaultdict 
n,m = map(int,input().split())
py = []
for i in range(m):
    p,y = map(int,input().split())
    py.append([p,y])
spy = sorted(py,key=lambda x:x[1])

cnt = [0]*n
id =  defaultdict(int)
for i in spy:
    p,y = i
    cnt[p-1] += 1
    id[(p,y)] = str(p).zfill(6)+str(cnt[p-1]).zfill(6)

for i in py:
    p,y = i
    print(id[(p,y)])
### BUGGY CODE ###

#!/usr/bin/env python3

MOD = 10**9
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

N = int(input())
A = list(map(int, input().split()))
dic = {}
for a in A:
    if a in dic: dic[a] += 1
    else: dic[a] = 1

C = {0:0}

for i in range(1, 10*10**5+1):
    C[i] = i*(i-1)//2

ans = []
for i in range(N):
    dic2 = dic.copy()
    dic2[A[i]] -= 1
    a = 0

    for k, v in dic2.items():
        a += C[v]

    ans.append(a)


for a in ans:
    print(a)


### FIXED CODE ###

#!/usr/bin/env python3

MOD = 10**9
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

N = int(input())
A = list(map(int, input().split()))
dic = {}
for a in A:
    if a in dic: dic[a] += 1
    else: dic[a] = 1

C = {0:0}

sum_ni = 0
for i in range(1, N+1):
    C[i] = i*(i-1)//2

D = {}
for k, v in dic.items():
    sum_ni += C[v]


for k, v in dic.items():
    D[k] = sum_ni - C[dic[k]] + C[dic[k]-1]

for i in range(N):
    print(D[A[i]])
### BUGGY CODE ###

import numpy as np

M = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))

zero = np.zeros(60, dtype=np.int64)
one = np.ones(60, dtype=np.int64)
pow2 = (2 ** np.arange(60, dtype=np.int64)) % M


def bitcnt(a):
    j = 0
    bits = np.zeros(60, dtype=np.int64)
    while a:
        bits[j] = a & 1
        a >>= 1
        j += 1
    return bits


ans = 0
a1 = bitcnt(A[0])
a0 = one - a1
for i in range(1, N):
    bits1 = bitcnt(A[i])
    bits0 = one - bits1
    ans += np.sum(pow2 * (a0 * bits1 % M) % M) % M
    ans %= M
    ans += np.sum(pow2 * (a1 * bits0 % M) % M) % M
    ans %= M
    a1 += bits1
    a1 %= M
    a0 += bits0
    a0 %= M

print(ans)


### FIXED CODE ###

M = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))

zero = [0] * 60
one = [1] * 60
pow2 = [2 ** i % M for i in range(60)]


def bitcnt(a):
    j = 0
    bits = [0] * 60
    while a:
        bits[j] = a & 1
        a >>= 1
        j += 1
    return bits


ans = 0
a1 = bitcnt(A[0])
a0 = [(x + 1) % 2 for x in a1]
for i in range(1, N):
    a = A[i]
    for j in range(60):
        b1 = a & 1
        a >>= 1
        if b1:
            ans += pow2[j] * a0[j] % M
            a1[j] += 1
        else:
            ans += pow2[j] * a1[j] % M
            a0[j] += 1
        ans %= M

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

N,M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)

for i in range(M):
    A[0] //= 2
    A = sorted(A,reverse=True)

print(sum(A))

### FIXED CODE ###

import heapq
N, M = [int(_) for _ in input().split()]
A = [-int(_) for _ in input().split()]

heapq.heapify(A)

for _ in range(M):
    a = heapq.heappop(A)
    heapq.heappush(A, -(-a//2))

print(-sum(A))