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

N,Ma,Mb = map(int,input().split())
ABC = [list(map(int,input().split())) for _ in [0]*N]
INFTY = 10**8
dp = [[[INFTY]*10*(N+1) for _ in [0]*10*(N+1)] for _ in [0]*(N+1)]
dp[0][0][0] = 0
for i in range(1,N+1):
    a,b,c = ABC[i-1]
    for j in range(10*(N+1)):
        for k in range(10*(N+1)):
            dp[i][j][k] = dp[i-1][j][k]
            if j-a>=0 and k-b>=0:
                dp[i][j][k] = min(dp[i][j][k],dp[i-1][j-a][k-b]+c)
ans = min(dp[-1][Ma*k][Mb*k] for k in range(1,(10*(N+1)-1)//max(Ma,Mb)+1))
if ans == INFTY : ans = -1
print(ans)

### FIXED CODE ###

N,*M = map(int,input().split())
abc = [list(map(int,input().split())) for _ in [0]*N]
INF = 100*40*100
dp = [[[INF]*500 for _ in [0]*500] for _ in [0]*(N+1)]
dp[0][0][0] = 0
for i in range(1,N+1):
    a,b,c = abc[i-1]
    for j in range(410):
        for k in range(410):
            dp[i][j][k] = min(dp[i-1][j][k],dp[i-1][j-a][k-b]+c)
ans = min([dp[-1][M[0]*i][M[1]*i] for i in range(1,1+400//(max(M)))])
if ans == INF:ans=-1
print(ans)
### BUGGY CODE ###

a=int(input())
list1=[1,2,3,4,5,6,7,8,9]
i=1
while(i<=a) :
  #print (list1)
  if i!=a :
    k=list1.pop(0)
    k=str(k)
    if int(k[-1])==0 :
      list1.append(int(str(k)+'0'))
      list1.append(int(str(k)+'1'))
      i+=1
    elif int(k[-1])==9 :
      list1.append(int(str(k)+'8'))
      list1.append(int(str(k)+'9'))
      i+=1
    else :
      list1.append(int(str(k)+str(int(k[-1])-1)))
      list1.append(int(str(k)+str(int(k[-1]))))
      list1.append(int(str(k)+str(int(k[-1])+1)))
      i+=1
  else :
    print(list1[0])
    break


### FIXED CODE ###

from collections import deque
a=int(input())
list1=deque([1,2,3,4,5,6,7,8,9])
i=1
while(i<=a) :
  #print (list1)
  if i!=a :
    k=list1.popleft()
    k=str(k)
    if int(k[-1])==0 :
      list1.append(int(str(k)+'0'))
      list1.append(int(str(k)+'1'))
      i+=1
    elif int(k[-1])==9 :
      list1.append(int(str(k)+'8'))
      list1.append(int(str(k)+'9'))
      i+=1
    else :
      list1.append(int(str(k)+str(int(k[-1])-1)))
      list1.append(int(str(k)+str(int(k[-1]))))
      list1.append(int(str(k)+str(int(k[-1])+1)))
      i+=1
  else :
    print(list1[0])
    break
### BUGGY CODE ###

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, V, U = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]

if V == U:
    print(0)
    exit()

V -= 1
U -= 1
graph = [[] for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

# 深い方に逃げるべき
# 子どものうち一番深い場所の深さ
children_depths = [-1 for _ in range(N)]
parents = [None for _ in range(N)]

stack = [(U, None)]
while stack:
    v, parent = stack.pop()
    parents[v] = parent
    for u in graph[v]:
        if u == parent:
            continue
        stack.append((u, v))

v = V
dist = 1
while parents[v] != U:
    v = parents[v]
    dist += 1

stack = []
for v in range(N):
    if len(graph[v]) == 1:
        stack.append((v, 0))
while stack:
    v, depth = stack.pop()
    if v is None:
        continue
    children_depths[v] = max(children_depths[v], depth)
    stack.append((parents[v], depth + 1))

# 何回親側に上がるか
p_cnt = 0
v = V
ans = 0
while dist > 0:
    ans = max(ans, dist - 1 + children_depths[v] + p_cnt)
    v = parents[v]
    p_cnt += 1
    dist -= 2
print(ans)


### FIXED CODE ###

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, V, U = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]

V -= 1
U -= 1
graph = [[] for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

# 深い方に逃げるべき
# 子どものうち一番深い場所の深さ
children_depths = [0] * N
parents = [None] * N

stack = [(U, None)]
vs = []
while stack:
    v, parent = stack.pop()
    parents[v] = parent
    vs.append(v)
    for u in graph[v]:
        if u == parent:
            continue
        stack.append((u, v))
vs.reverse()
for v in vs:
    if parents[v] is not None:
        children_depths[parents[v]] = max(children_depths[parents[v]], children_depths[v] + 1)

v = V
dist = 1
while parents[v] != U:
    v = parents[v]
    dist += 1

# 何回親側に上がるか
p_cnt = 0
v = V
ans = 0
while dist > 0:
    ans = max(ans, dist - 1 + children_depths[v] + p_cnt)
    v = parents[v]
    p_cnt += 1
    dist -= 2
print(ans)
### BUGGY CODE ###

s = input()
k = int(input())

k_list = set(s) 
for i in range(2, len(s)+1):
    for j in range(len(s)+1-i):
        sub = s[j:j+i]
        k_list.add(sub)

k_list = list(k_list)
k_list.sort()
print(k_list[k-1])

### FIXED CODE ###

s = input()
k = int(input())

kn = len(s) * k
k_list = set(s)

for i in range(2, k+1):
    for j in range(len(s)):
        k_list.add(s[j:j+i])

k_list = list(k_list)
k_list.sort()
print(k_list[k-1])
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
for i in range(N-1):
    print(A.count(i+1))
print("0")


### FIXED CODE ###

n = int(input())
 
boss_list = map(int, input().split())
 
employee_list = [0] * n
 
for boss in boss_list:
	employee_list[boss - 1] += 1
 
for employee in employee_list:
	print(employee)
### BUGGY CODE ###

N,M = map(int,input().split())
L = [list(map(int,input().split())) for i in range(M)]
flag = False
j = 0
while (0 <= j <= len(L)-1):
  k = L[j][1]
  if ([1,k] in L):
    if ([k,N] in L):
      flag = True
      break
    else:
      j += 1
  else:
    j += 1
if flag:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

### FIXED CODE ###

N,M = map(int,input().split())
L = [list(map(int,input().split())) for i in range(M)]
J = [False]*(N+1)
K = [False]*(N+1)
J[0] = False
K[N] = False
J[1] = False
K[1] = False
for j in range(M):
  if L[j][0] == 1:
    J[L[j][1]] = True
for k in range(M):
  if L[k][1] == N:
    K[L[k][0]] = True
flag = False
for l in range(N+1):
  if J[l] and K[l]:
    flag = True
    break
if flag:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')
### BUGGY CODE ###

n = int(input())
arr = list(map(int,input().split()))
for i in range(int(input())):
    b,c = map(int,input().split())
    for i in range(len(arr)):
        if arr[i] == b:
            arr[i] = c
    print(sum(arr))

### FIXED CODE ###

from collections import Counter

N = int(input())
A = list(map(int, input().split()))
count = Counter(A)
S = sum(A)

for _ in range(int(input())):
    b, c = map(int, input().split())
    k = count[b]
    count[b] = 0
    count[c] += k
    S += (c - b) * k
    print(S)
### BUGGY CODE ###

import collections

x = collections.deque(input())
n = int(input())
y = 0

for i in range(n):
    a = input()
    if a[0] == "1":
      x.reverse()
    else:
      a, b, c = a.split()
      a = int(a)
      b = int(b)

      if b == 2:
          x.append(c)
      elif b == 1:
          x.appendleft(c)

print("".join(x))

### FIXED CODE ###

import collections

x = collections.deque(input())
n = int(input())
rev = False

for i in range(n):
    y = input().split()
    if len(y) == 1:
      rev = not rev
    elif rev:
      if int(y[1]) == 2:
          x.appendleft(y[2])
      else:
          x.append(y[2])
    else:
      if int(y[1]) == 2:
          x.append(y[2])
      else:
          x.appendleft(y[2])

if rev:
  x.reverse()

print("".join(x))
### BUGGY CODE ###

from itertools import accumulate
N, K = map(int, input().split())
As = list(map(int, input().split()))

dp1 = [[0] * (K+1)]
dp1[0][0] = 1
for a in As:
    ndp = []
    pdp = dp1[-1]
    for i in range(K+1):
        ndp.append(pdp[i] if i < a else pdp[i] + pdp[i-a])
    dp1.append(ndp)

dp2 = [[0] * (K+1)]
dp2[0][0] = 1
for a in reversed(As):
    ndp = []
    pdp = dp2[-1]
    for i in range(K+1):
        ndp.append(pdp[i] if i < a else pdp[i] + pdp[i-a])
    dp2.append(ndp)
accs2 = [list(accumulate(dp)) + [0] for dp in dp2]

ans = 0
for i in range(1, N+1):
    a = As[i-1]
    if a >= K:
        continue
    dp = dp1[i-1]
    acc2 = accs2[N-i]
    for y in range(K+1):
        if dp[y] == 0:
            continue
        t = K-y-a-1
        if acc2[K-y-1] > acc2[t if t >= 0 else -1]:
            break
    else:
        ans += 1
print(ans)


### FIXED CODE ###

from itertools import accumulate

def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    
    nonzeros = [1]
    for a in As:
        ndp = nonzeros[-1]
        if a <= K:
            ndp |= (nonzeros[-1] % (1 << (K-a))) << a
        nonzeros.append(ndp)
    dp = [0] * (K+1)
    dp[0] = 1
    acc = list(accumulate(dp)) + [0]
    ans = 0
    for i in range(N, 0, -1):
        a = As[i-1]
        ndp = []
        for j in range(K+1):
            t = dp[j] if j < a else dp[j] + dp[j-a]
            ndp.append(0 if t == 0 else 1)
        dp = ndp
        if a < K:
            nonzero = nonzeros[i-1]
            for y in range(K+1):
                if nonzero & 1:
                    t = K-y-a-1
                    if acc[K-y-1] > acc[t if t >= 0 else -1]:
                        break
                nonzero >>= 1
            else:
                ans += 1
        acc = list(accumulate(dp)) + [0]
    
    print(ans)

main()
### BUGGY CODE ###

n=int(input())
a=list(map(str,input().split()))
b=str(a[0])
if n%2==0:
    for i in range(1,n):
        if i%2==1:
            b=a[i]+' '+b
        else:
            b=b+' '+a[i]
    print(b)
else:
    for i in range(1,n):
        if i%2==0:
            b=a[i]+' '+b
        else:
            b=b+' '+a[i]
    print(b)

### FIXED CODE ###

from collections import deque
n=int(input())
a=list(map(str,input().split()))
l=deque()
if n%2==0:
    for i in range(n):
        if i%2==1:
            l.appendleft(a[i])
        else:
            l.append(a[i])
    print(" ".join(map(str,l)))
else:
    for i in range(n):
        if i%2==0:
            l.appendleft(a[i])
        else:
            l.append(a[i])
    print(" ".join(map(str,l)))
### BUGGY CODE ###

N, M = map(int, input().split())
cards = set(range(1, N+1))
for i in range(M):
    L, R = map(int, input().split())
    cards &= set(range(L, R+1))
print(len(cards))


### FIXED CODE ###

N, M = map(int, input().split())
maxl = 0
minr = N + 1
for i in range(M):
    L, R = map(int, input().split())
    maxl = max(maxl, L)
    minr = min(minr, R)
print(max(0, minr - maxl + 1))
### BUGGY CODE ###

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

MOD = 10**9 +7
dp = [0] * (1<<n)

pair_dic = {}
for i in range(n+1):
    pair_dic[i] = []

for i in range(1<<n):
    pair_dic[ bin(i).count('1') ].append(i)

dp[0] = 1
for i in range(n):
    for j in pair_dic[i]:
        for k in range(n):
            if( (a[i][k] == 1) & ( ((j&(1<<k)) >>k == 0 ) )):
                dp[j + (1<<k)] += dp[j]
                dp[j + (1<<k)] = dp[j + (1<<k)] % MOD


print(dp[-1])

### FIXED CODE ###

def main():

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

    MOD = 10**9 +7
    dp = [0] * (1<<n)

    pair_dic = {}
    for i in range(n+1):
        pair_dic[i] = []

    for i in range(1<<n):
        pair_dic[ bin(i).count('1') ].append(i)

    dp[0] = 1

    for i in range(n):
        for k in range(n):
            if(a[i-1][k] == 0):
                continue
            for j in pair_dic[i]:
                if(  ((j&(1<<k)) >>k == 0 ) ):
                    dp[j + (1<<k)] += dp[j]
                    dp[j + (1<<k)] = dp[j + (1<<k)] % MOD

    print(dp[-1])

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

import numpy as np
from numba import njit

n=int(input())
a=np.array(list(map(int, input().split())))
q=int(input())
a_sum= np.sum(a)


@njit
def func(a,b,c,a_sum):
  count=np.count_nonzero(a==b)
  a[a==b]=c
  a_sum += count*(c-b)
  return a,a_sum
  
for i in range(q):
  b,c=map(int, input().split())
  a,a_sum=func(a,b,c,a_sum)
  print(a_sum)

### FIXED CODE ###

import collections

N=int(input())
A=list(map(int,input().split()))
X=collections.Counter(A)
Q=int(input())

ans=sum(A)
for i in range(Q):
  B,C=map(int,input().split())
  ans+=(C-B)*X[B]
  print(ans)
  X[C]+=X[B]
  X[B]=0
### BUGGY CODE ###

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

ans=0
for i in range(N-1):
  for j in range(i+1,N):
    ans+=A[i]^A[j]
print(ans%(10**9+7))

### FIXED CODE ###

N=int(input())
M=10**9+7
A=[int(x) for x in input().split()]

ans=p=0
for i in range(60):
  one=sum([a>>p&1 for a in A])
  zero=N-one
  p+=1
  ans+=(one*zero)*2**i
  ans%=M
  #print(one,zero)
print(ans)
### BUGGY CODE ###

import copy
a,b,c,k = map(int,input().split())

if a == b == c:
    print(0)
    exit()

cnt = 0
while True:
    aa = copy.deepcopy(a)
    bb = copy.deepcopy(b)
    cc = copy.deepcopy(c)

    a = bb + cc
    b = aa+cc
    c = aa + bb
    cnt += 1
    if abs(a-b) >= 10**18:
        print('Unfair')
        break
    if cnt == k:
        print(a - b)
        break


### FIXED CODE ###

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

x = abs(a-b)
if x > 10**18:
    print('Unfair')
else:
    if k % 2 == 0:
        print(a - b)
    else:
        print(b-a)
### BUGGY CODE ###

s=input()
kyonen=2019
modlist=[]
for i in range(len(s)):
    modlist.append(int(s[i:len(s)])%kyonen)
modlist.sort()
now=modlist[0]
nowc=1
ans=0
if modlist[0]==0:
    ans+=1
for i in range(1,len(modlist)):
    if modlist[i]==0:
        ans+=1
    if modlist[i]==now:
        nowc+=1
    else:
        if nowc>=2:
            ans+=int(nowc*(nowc-1)/2)
        nowc=1
        now=modlist[i]

if nowc>=2:
    ans+=int(nowc*(nowc-1)/2)

print(ans)

### FIXED CODE ###

s=input()
N=len(s)
kyonen=2019
ans=0

#alistつくる
alist=[]
for i in reversed(range(N)):
    alist.append((int(s[i])*pow(10,(N-1-i),kyonen))%kyonen)

#累積和とる
ruisekiwa=[0]
for i in range(N):
    ruisekiwa.append((ruisekiwa[-1]+alist[i])%kyonen)

#累積和リストの中から、同じ数字の組み合わせの個数を求める
kazoe=[0]*2019
for i in range(N+1):
    kazoe[ruisekiwa[i]]+=1

for i in range(2019):
    if kazoe[i]>=2:
        ans+=int(kazoe[i]*(kazoe[i]-1)/2)

if ruisekiwa[N]==0:
    ans+=1

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

#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
for j in range(100000):
    check = [1]*n
    flg = False
    flg2 = False
    for i in range(n):
        if len(a[i]) == 0 or check[i] == 0:
            continue
        (x,y) = a[i].popleft()
        flg2 = True
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            a[y-1].popleft()
            flg = True
            check[y-1] = 0
        else:
            a[i].appendleft((x,y))
    if flg:
        ans += 1
    if not flg2:
        print(ans)
        quit()
for i in a:
    if len(i) != 0:
        print(-1)
        quit()
print(n*(n-1)//2)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
import time
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
s = time.time()
for j in range(n*(n-1)//2+1):
    check = [1]*n
    flg = False
    flg2 = False
    if time.time() - s > 1.6:
        print(n*(n-1)//2)
        quit()
    for i in range(n):
        if len(a[i]) == 0 or check[i] == 0:
            continue
        (x,y) = a[i].popleft()
        flg2 = True
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            a[y-1].popleft()
            flg = True
            check[y-1] = 0
        else:
            a[i].appendleft((x,y))
    if flg:
        ans += 1
    if not flg:
        for i in a:
            if len(i) != 0:
                print(-1)
                quit()
    if not flg2:
        print(ans)
        quit()
### BUGGY CODE ###

import numpy as np

N = int(input())
A = np.sort(list(map(int,input().split())))[::-1]
ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        a = A[i]
        b = A[j]
        C = A[j+1:]
        J = (C<a+b) * (C>a-b)
        if (np.any(J)):
            ans += np.size(C[J])

print(ans)

### FIXED CODE ###

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

#N=len(sticks)
sticks = sorted(sticks1, reverse=True)
#sticks.sort(reverse = True)
count = 0
jmax = N-2
kmax = N-1
i=0
while i<N-2:
    j= i+1
    while j<jmax+1:
        k=kmax
        while j<k:
            #sticks[i]>sticks[j]>sticks[k]
            if sticks[i]<sticks[j]+sticks[k]:
                count += k-j
                kmax = k
                break
            else:
                k -= 1
                continue
        jmax = kmax-1
        j += 1
    kmax = N-1
    jmax = N-2
    i += 1
      
print(count)
### BUGGY CODE ###

from itertools import permutations

def WarshallFloyd(M):
    N = len(M)
    for k in range(N):
        for j in range(N):
            for i in range(N):
                M[i][j] = min(M[i][j], M[i][k] + M[k][j])
    return M

N, M, K = map(int, input().split())
R = [int(i) - 1 for i in input().split()]
E = [[0] * N for _ in range(N)]
for a, b, c in (map(int, input().split()) for _ in range(M)):
    a -= 1; b -= 1
    E[a][b] = E[b][a] = c

E = WarshallFloyd(E)
ans = min(sum(E[p[i]][p[i + 1]] for i in range(K - 1)) for p in permutations(R))
print(ans)


### FIXED CODE ###

from itertools import permutations

def WarshallFloyd(M):
    N = len(M)
    for k in range(N):
        for j in range(N):
            for i in range(N):
                M[i][j] = min(M[i][j], M[i][k] + M[k][j])
    return M

INF = 1e10

N, M, K = map(int, input().split())
R = [int(i) - 1 for i in input().split()]
E = [[INF] * N for _ in range(N)]
for a, b, c in (map(int, input().split()) for _ in range(M)):
    a -= 1; b -= 1
    E[a][b] = E[b][a] = c

E = WarshallFloyd(E)
ans = min(sum(E[p[i]][p[i + 1]] for i in range(K - 1)) for p in permutations(R))
print(ans)
### BUGGY CODE ###

N,R = map(int,input().split())
id = [0]*N
ans = 0
for i in range(R):
  A,B = map(int,input().split())
  for j in range(B-A+1):
    id[j+A-1]+=1
for i in id:
  if i == R:
    ans += 1
print(ans)

### FIXED CODE ###

N,R = map(int,input().split())
min = 0
max = 10000000
ans = 0
for i in range(R):
  A,B = map(int,input().split())
  if A > min:
    min = A
  if B < max:
    max = B
if min < max:
  ans = max - min + 1
elif min == max:
  ans = 1
print(ans)
### BUGGY CODE ###

from queue import Queue

def inside(x, l, r):
    return l <= x < r

if __name__ == '__main__':
    h, w = map(int, input().split())

    a = [list(input()) for _ in range(h)]

    qu = Queue()

    nokori = h*w
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                nokori -= 1
                qu.put(i*w + j)

    ans = 0
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    while nokori:
        ans += 1
        qu2 = Queue()
        while not qu.empty():
            i0, j0 = divmod(qu.get(), w)
            for k in range(4):
                ni = i0 + dx[k]
                nj = j0 + dy[k]
                if not (inside(ni, 0, h) and inside(nj, 0, w)):
                    continue
                if a[ni][nj] == '.':
                    a[ni][nj] = '#'
                    nokori -= 1
                    qu2.put(ni*w+nj)
        qu = qu2
    print(ans)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
G = [input() for _ in range(H)]
dist = [0]*(H*W)
bn = 0
B = deque()
geta = W
for i, g in enumerate(G):
    for j, f in enumerate(g):
        if f == '#':
            bn += 1
            B.append(i*geta + j)
visited = set(B)
while bn < H*W:
    if not B:
        break
    dh, dw = divmod(B.pop(), geta)
    dhw = dh * geta + dw
    for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        ni, nj = dh + di, dw + dj
        if not (0 <= ni <= H - 1) or not (0 <= nj <= W - 1):
            continue
        nij = ni * geta + nj
        if nij in visited or G[ni][nj] == '#':
            continue
        visited.add(nij)
        dist[nij] = 1 + dist[dhw]
        B.appendleft(nij)
print(max(dist))
### BUGGY CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools


sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


N, M = LI()
P, Y = [], []
for i in range(M):
    j, k = LI()
    P.append(j)
    Y.append(k)

city_records = [[]for i in range((max(P)+1))]
for p, y in zip(P, Y):
    #  print('p,y', p, y)
    #  print('city_records[p]', city_records[p])
    city_records[p].append([p, y])

#  print(city_records)

for i in range(len(city_records)):
    if city_records[i] == []:
        continue
    city_records[i].sort(key=lambda x: x[1])

#  print(city_records)

for p, y in zip(P, Y):
    order = (city_records[p].index([p, y])) + 1
    print(str(p).zfill(6) + str(order).zfill(6))


### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools


sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


N, M = LI()
P, Y = [], []
for i in range(M):
    j, k = LI()
    P.append(j)
    Y.append(k)

#  N = 10**5
#  M = 10**5
#  P, Y = [], []
#  for i in range(M):
#      P.append(10)
#      Y.append(i*100)

city_records = [[]for i in range(10**6)]
for p, y in zip(P, Y):
    #  print('p,y', p, y)
    #  print('city_records[p]', city_records[p])
    city_records[p].append(y)

#  print(city_records)

for i in range(len(city_records)):
    if city_records[i] == []:
        continue
    city_records[i].sort()

#  print(city_records)

for p, y in zip(P, Y):
    #  order = (city_records[p].index(y)) + 1
    order = bisect.bisect_left(city_records[p], y) + 1
    print(str(p).zfill(6) + str(order).zfill(6))
### BUGGY CODE ###

N = int(input())
li = input().rstrip().split()

le =[0]*N
le2 = [0]*N

for i in range(0,N):
    le[i]=int(li[i])

for i in range(0,N):
    le2[i]=le[i]-i-1
    le2.sort()

b = le2[int(N/2)]
sum = 0
for i in range(0,N):
    sum = sum + abs(le[i]-i-1-b)

print(sum)

### FIXED CODE ###


N = int(input())
li = input().rstrip().split()

le =[0]*N
le2 = [0]*N

for i in range(0,N):
    le[i]=int(li[i])


for i in range(0,N):
    le2[i]=le[i]-i-1
le2.sort()


b = le2[int(N/2)]
sum = 0
for i in range(0,N):
    sum = sum + abs(le[i]-i-1-b)

print(sum)