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

def dfs(n):
    adj = [chr(i+97) for i in range(26)]
    
    stack = ['a']
    combs = []
    while stack:
        node = stack.pop(0)
        if len(node) == n:
            combs.append(node)
        else:
            limit = ord(max(node))%97+2
            for child in adj[:limit]:
                cand = node+child
                stack.append(node+child)
    return combs

def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    res = dfs(n)
    for ans in res:
        print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def dfs(s,n,adj):
    adj = 'abcdefghij'
    if len(s) == n:
        print(s)
    else:
        for child in adj[:len(set(s))+1]:
            dfs(s+child,n,adj)
    return -1

def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    adj = 'abcdefghij'
    dfs('a',n,adj)


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

import sys
readline=sys.stdin.readline

N,K = map(int,readline().split())
A = list(map(int,readline().split()))
def calc(A):
    B = [0] * len(A)
    for i in range(len(A)):
        B[max(0,i - A[i])] += 1
        if i + A[i] + 1 < len(A):
            B[i + A[i] + 1] -= 1
    for i in range(1,len(B)):
        B[i] = B[i - 1] + B[i]
    return B

for i in range(K):
  A = calc(A)
  if len(set(A)) == 1 and A[0] == N:
    print(*A)
    break
else:
  print(*A)



### FIXED CODE ###

import sys
readline=sys.stdin.readline

N,K = map(int,readline().split())
A = list(map(int,readline().split()))
def calc(A):
    B = [0] * len(A)
    for i in range(len(A)):
        B[max(0,i - A[i])] += 1
        if i + A[i] + 1 < len(A):
            B[i + A[i] + 1] -= 1
    for i in range(1,len(B)):
        B[i] = B[i - 1] + B[i]
    return B

for i in range(K):
  A = calc(A)
  if len(set(A)) == 1 and A[0] == N:
    print(*A)
    break
else:
  print(*A)
### BUGGY CODE ###

N,K = list(map(int,input().split()))
TDlist = []

for x in range(0,N):
    TDlist.append(list(map(int,input().split())))

sorted_list = sorted(TDlist, key = lambda x: x[1], reverse=True)
kinds = []
seconds = []
answer = 0

for x in sorted_list[:K]:
    if not x[0] in kinds:
        kinds.append(x[0])
    else:
        seconds.append(x[1])
    answer += x[1]

answer += len(kinds)**2
score = answer
max_score = answer

for x in sorted_list[K:]:
    if seconds == []:
        break
    if x[0] in kinds:
        continue
    kinds.append(x[0])
    y = seconds.pop()
    score += (x[1] - y) + (len(kinds)*2 -1)
    max_score = max(score,answer)
    

answer = max(answer,max_score)

print(answer)

### FIXED CODE ###

N,K = list(map(int,input().split()))
TDlist = []

for x in range(0,N):
    TDlist.append(list(map(int,input().split())))

TDlist= sorted(TDlist, key = lambda x: x[1],reverse=True)
kinds = set()
seconds = []
answer = 0

for x in TDlist[:K]:
    if not x[0] in kinds:
        kinds.add(x[0])
    else:
        seconds.append(x[1])
    answer += x[1]

answer += len(kinds)**2
score = answer

for x in TDlist[K:]:
    if seconds == []:
        break
    if x[0] in kinds:
        continue
    kinds.add(x[0])
    y = seconds.pop()
    score += (x[1] - y) + (len(kinds)*2 -1)
    answer = max(score,answer)

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

def sousa(k,hand,v):
    if k==0:
        # print(k,sum(hand),hand,v)
        ans.append(sum(hand))
        return
    if len(v)>0:
        # 左から取る
        sousa(k-1,hand+[v[0]],v[1:])
        # 右から取る
        sousa(k-1,hand+[v[-1]],v[:-1])

    if len(hand)>0:
        # 右に入れる
        hand.sort()
        array=[hand[0]]
        sousa(k-1,hand[1:],v+array)
        # 左に入れる
        sousa(k-1,hand[1:],array+v)



n,k=map(int,input().split())
v=list(map(int,input().split()))
ans=[0]
sousa(k,[],v)
# print(ans)
print(max(ans))


### FIXED CODE ###

n,k=map(int,input().split())
v=list(map(int,input().split()))
ans=[]
for lhs in range(k+1):
    for rhs in range(k-lhs+1):
        if lhs+rhs<=n:
            array=v[:lhs]+v[n-rhs:]
        else:
            array=v[:]
        # print(v[:lhs],v[n-rhs:])
        for i in range(k+1-lhs-rhs):
            array.sort()
            ans.append(sum(array[i:]))
# print(ans)
print(max(ans))
### BUGGY CODE ###

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

if n % k == 0:
  print(0)
  exit()

while True:
  n = abs(n - k)
  if n >= now:
    break
  now = n
print(now)

### FIXED CODE ###

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

now = abs((n % k) - k)
if now < n%k:
  print(now)
else:
  print(n%k)
### BUGGY CODE ###

def update(BIT,index,letter,value):
    while index < len(BIT):
        BIT[index][letter] += value
        index += index&-index

def sumQuery(BIT,index):
    letters = [0]*26
    while index > 0:
        for i in range(26):
            letters[i] += BIT[index][i]

        index -= index&-index

    return letters

def rangeQuery(BIT,l,r,ans):
    right = sumQuery(BIT,r)
    left = sumQuery(BIT,l-1)
    count = 0
    for i in range(26):
        right[i] -= left[i]
        if right[i] > 0:
            count += 1

    ans.append(count)

def main():
    n = int(input())
    s = list(input())
    q = int(input())
    BIT = [[0 for i in range(26)] for j in range(n+1)]
    ans = []

    for i in range(n):
        update(BIT,i+1,ord(s[i])-ord('a'),1)

    for i in range(q):
        query,index,c = map(str,input().split())
        query = int(query)
        if query == 1:
            index = int(index)
            update(BIT,index,ord(s[index-1])-ord('a'),-1)
            s[index-1] = c
            update(BIT,index,ord(s[index-1])-ord('a'),1)
        else:
            l,r = int(index),int(c)
            rangeQuery(BIT,l,r,ans)

    for i in ans:
        print(i)


main()


### FIXED CODE ###

def update(BIT,index,letter,value):
    while index < len(BIT):
        BIT[index][letter] += value
        index += index&-index

def sumQuery(BIT,index):
    letters = [0]*26
    while index > 0:
        for i in range(26):
            letters[i] += BIT[index][i]

        index -= index&-index

    return letters

def rangeQuery(BIT,l,r,ans):
    right = sumQuery(BIT,r)
    left = sumQuery(BIT,l-1)
    count = 0
    for i in range(26):
        right[i] -= left[i]
        if right[i] > 0:
            count += 1

    ans.append(count)

def main():
    n = int(input())
    s = list(input())
    q = int(input())
    BIT = [[0 for i in range(26)] for j in range(n+1)]
    ans = []

    for i in range(n):
        update(BIT,i+1,ord(s[i])-ord('a'),1)

    for i in range(q):
        query,index,c = map(str,input().split())
        query = int(query)
        if query == 1:
            index = int(index)
            update(BIT,index,ord(s[index-1])-ord('a'),-1)
            s[index-1] = c
            update(BIT,index,ord(s[index-1])-ord('a'),1)
        else:
            l,r = int(index),int(c)
            rangeQuery(BIT,l,r,ans)

    for i in ans:
        print(i)


main()
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        ok, ng = j, n
        while ng - ok > 1:
            mid = (ok + ng) // 2
            if l[mid] < l[i] + l[j]:
                ok = mid
            else:
                ng = mid
        ans += ok - j
print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(n):
  for j in range(i + 1, n):
    lf = j
    rf = n
    while rf - lf > 1:
      md = (lf + rf) // 2
      if l[md] < l[i] + l[j]:
        lf = md
      else:
        rf = md
    ans += lf - j
    #print(i, j, ans)
print(ans)
### BUGGY CODE ###

N = int(input())
S = [list(input()) for i in range(N)]
T = ['' for m in range(N)]

for l in range(N):
  S[l].sort()
  T[l] = ''.join(S[l])

ans = 0
for j in range(N):
  for k in range(j+1,N):
    if j != k:
      if S[j][0] == S[k][0]:
        if S[j][9] == S[k][9]:
          if T[j] == T[k]:
            ans += 1

print(ans)

### FIXED CODE ###

from operator import itemgetter
N = int(input())
S = [list(input()) for i in range(N)]

for l in range(N):
  S[l].sort()
  S[l] = ''.join(S[l]) 

S.sort()

X = []
p = 1

for j in range(N-1):
  if S[j] == S[j+1]:
    p +=1
  else:
    X.append(p)
    p = 1
X.append(p)


def comb(n):
  if n == 2: return 1
  else:
    return int(n*(n-1)/2)

ans = 0

for k in range(len(X)):
  ans += comb(X[k])

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

N, Q = map(int,input().split())
S = input().replace("G","").replace("T","")

for _  in range(Q):
  l, r = map(int,input().split())
  x = S[l-1:r]
  if(x):
    print(x.count("AC"))
  else:
    print(0)

### FIXED CODE ###

N, Q = map(int,input().split())
S = input()
t = [0]*(N+1)
for i in range(N):
  t[i+1] = t[i] + (1 if S[i:i+2] == "AC" else 0)
for _ in range(Q):
  l, r = map(int,input().split())
  print(t[r-1] - t[l-1])
### BUGGY CODE ###

N = int(input())
L = [int(input()) for i in range(N)]

ans = set()
     
for x in L:
    if L.count(x) % 2 == 1:
        ans.add(x)

print(len(ans))

### FIXED CODE ###

import collections

N = int(input())
L = [int(input()) for i in range(N)]

M = collections.Counter(L)
C = M.most_common()
cnt = 0

for x in C:
    if x[1] % 2 == 1:
        cnt += 1
        
print(cnt)
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
    a.append(list(input()))
for i in range(n):
    a[i].extend(a[i])
for i in range(n):
    a.append(a[i])


x = 0

for i in range(n):
    for j in range(n):
        for k in range(j+1):
            if a[i+j][k]==a[i+k][j]:
                continue
            else:
                break
        else:
            continue
        break
    else:
        x += 1

print(n*x)

 

### FIXED CODE ###

N = int(input())
S = []
for i in range(N):
    S.append(input())

def check(S, A, B):
    for i in range(N):
        for j in range(i+1, N):
            if S[i][j] != S[j][i]:
                return 0
    return 1

cnt = 0
for i in range(N):
    cnt += check(S[i:] + S[:i], 0, 0)
print(cnt * N)
### BUGGY CODE ###

N, M = map(int, input().split(" "))
stores = []
for i in range(N):
    Ai, Bi = map(int, input().split(" "))
    tg_idx = -1
    for idx, s in enumerate(stores):
        if s[0] > Ai:
            tg_idx = idx
            break
    if tg_idx != -1:
        stores.insert(tg_idx, (Ai, Bi))
    else:
        stores.append((Ai, Bi))

    stock = 0
    unuse_idx = -1
    for idx, s in enumerate(stores):
        if stock <= M:
            stock += s[1]
        else:
            unuse_idx = idx
            break
    if unuse_idx != -1:
        stores = stores[:unuse_idx]

price = 0
for store in stores:
    if M <= store[1]:
        price += store[0] * M
        break
    else:
        price += store[0] * store[1]
        M -= store[1]
print(price)


### FIXED CODE ###

N, M = map(int, input().split(" "))
stores = []

for i in range(N):
    Ai, Bi = map(int, input().split(" "))
    stores.append((Ai, Bi))    

price = 0
for a, b in sorted(stores, key=lambda x: x[0]):
    if M <= b:
        price += a * M
        break
    else:
        price += a * b
        M -= b
print(price)
### BUGGY CODE ###

N,M=map(int, input().split())
A=sorted(map(int, input().split()))
BC=sorted([list(map(int,input().split())) for i in range(M)],key=lambda x: x[1],reverse=True)
from bisect import bisect_left
l=N
ans=0
numans=0
for m in range(M):
    r=bisect_left(A,BC[m][1])
    num=min(r,BC[m][0])
    if r:
        ans=ans+sum(A[r:])+BC[m][1]*num
        numans+=len(A[r:])+num
        A=A[num:r]
    else:
        break
ans+=sum(A[-(N-numans):])
print(ans)

### FIXED CODE ###

N,M=map(int, input().split())
import sys
def input(): return sys.stdin.readline().strip()
A=list(map(int, input().split()))
BC=[list(map(int,input().split())) for i in range(M)]
A.sort()
BC.sort(key=lambda x: x[1],reverse=True)
from bisect import bisect_left
ans=0
l=0
for m in range(M):
    if BC[m][0]<len(A)-l and A[BC[m][0]+l]<BC[m][1]:
        ans=ans+BC[m][1]*BC[m][0]
        l+=BC[m][0]
    else:     
        r=bisect_left(A[l:],BC[m][1])
        if r:
            ans=ans+BC[m][1]*r
            l+=r
        break
ans+=sum(A[l:])
print(ans)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

box = sorted([R,G,B],reverse=True)

count = 0
for x in range(0,N+1,box[0]):
    for y in range(0,N+1,box[1]):
        if x + y > N:
            continue
        z = (N - x - y) / box[2]
        if z >= 0 and z.is_integer():
            count += 1
print(count)

### FIXED CODE ###

R, G, B, N = map(int, input().split())

box = sorted([R,G,B],reverse=True)

count = 0
for x in range(0,N+1,box[0]):
    for y in range(0,N+1 - x ,box[1]):
        z = (N - x - y) / box[2]
        if z >= 0 and z.is_integer():
            count += 1
print(count)
### BUGGY CODE ###

def main():
    r, c, k = map(int, input().split())
    d = [[0]*c for _ in [0]*r]
    for _ in range(k):
        t1, t2, t3 = map(int, input().split())
        d[t1-1][t2-1] = t3
    dp = [[0]*4 for _ in [0]*c]
    dp[0][1] = d[0][0]
    for x in range(r):
        dp2 = [[0]*4 for _ in [0]*c]
        for y in range(c):
            for z in range(4):
                if y != c-1:
                    if z != 3:
                        dp[y+1][z+1] = max(dp[y+1]
                                           [z+1], dp[y][z]+d[x][y+1])
                    dp[y+1][z] = max(dp[y+1][z], dp[y][z])
            if x != r-1:
                dp2[y][1] = max(dp2[y][1],
                                max(dp[y])+d[x+1][y])
                dp2[y][0] = max(dp2[y][0], max(dp[y]))
        if x != r-1:
            dp = dp2
    print(max(dp[c-1]))


main()


### FIXED CODE ###

def main():
    r, c, k = map(int, input().split())
    d = [[0]*c for _ in [0]*r]
    for _ in range(k):
        t1, t2, t3 = map(int, input().split())
        d[t1-1][t2-1] = t3
    dp = [[0]*4 for _ in [0]*c]
    dp[0][1] = d[0][0]
    for x in range(r):
        dp2 = [[0]*4 for _ in [0]*c]
        for y in range(c):
            for z in range(4):
                if y != c-1:
                    if z != 3:
                        dp[y+1][z+1] = max(dp[y+1]
                                           [z+1], dp[y][z]+d[x][y+1])
                    dp[y+1][z] = max(dp[y+1][z], dp[y][z])
            if x != r-1:
                dp2[y][1] = max(dp2[y][1],
                                max(dp[y])+d[x+1][y])
                dp2[y][0] = max(dp2[y][0], max(dp[y]))
        if x != r-1:
            dp = dp2
    print(max(dp[c-1]))


main()
### BUGGY CODE ###

import collections
import math


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


N = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
ans = 0
for k, v in c.items():
    if v > 1:
        ans += combinations_count(v, 2)
total_ans = ans

for i in range(N):
    k_ball = A[i]
    if c[k_ball] > 2:
        print(
            total_ans
            - (combinations_count(c[k_ball], 2) - combinations_count(c[k_ball] - 1, 2))
        )
    elif c[k_ball] > 1:
        # 2
        print(total_ans - 1)
    else:
        print(total_ans)

### FIXED CODE ###

# 解き直し
import collections

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

total = 0
for v in c.values():
    total += v * (v - 1) // 2

for k_ball in A:
    cnt = c[k_ball]
    print(total - (cnt * (cnt - 1) // 2) + ((cnt - 1) * (cnt - 2) // 2))
### BUGGY CODE ###

k, s = map(int, input().split())
cnt = 0
lst = []

for i in range(k+1):
    for j in range(k+1):
        lst.append(i+j)

for i in range(len(lst)):
    for j in range(k+1):
        if lst[i]==s-j:
            cnt += 1

print(cnt)

### FIXED CODE ###

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

def main31():
    import itertools
    import functools
    import operator
    prod = functools.partial(functools.reduce, operator.mul)

    N = int(input())
    S = list(input())  # len:N

    S = sorted(S)  #  アルファベット順に並べ替え
    U = [0] * 26  #  ユニーク数数え上げ
    tmp = "0"
    count = 0
    u_count = 0
    for i in range(N):
        if i > 0:
            if tmp == S[i]:
                U[count] += 1
            else:
                tmp = S[i]
                count += 1
                U[count] += 1
        else:
            tmp = S[i]
            U[count] += 1

    for u in range(26):
        if U[u] != 0:
            u_count += 1

    U = sorted(U)

    for i in range(len(U)):
        if U[0] == 0:
            U.pop(0)

    count = 0

    for i in range(1, u_count+1):
        answer_list = list(itertools.combinations(U, i))
        count += sum(list(map(prod, answer_list)))

    a = 10 **9 + 7
    print(count % a)
main31()

### FIXED CODE ###

from collections import Counter
N = int(input())
S = input()
answer = 1
counter = Counter(S).most_common()

for i in range(len(counter)):
    answer = answer * (counter[i][1] + 1) % (10**9 + 7)

print(answer-1)
### BUGGY CODE ###

import numpy as np
import pprint
import math

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

s = min(n, b)
max_num = 0
for x in range(s + 1):
    tmp = math.floor(a * x / b) - a * math.floor(x / b)
    max_num = max(max_num, tmp)

print(max_num)


### FIXED CODE ###

import numpy as np
import pprint
import math

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

s = min(n, b - 1)
ans = math.floor(a * s / b) - a * math.floor(s / b)

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

N, M = map(int, input().split())
A = [int(i) for i in input().split()]
while M > 0:
    A.sort()
    A[-1]//= 2
    M -= 1
print(sum(A))

### FIXED CODE ###

from heapq import heapify, heappush, heappop
N, M = map(int, input().split())
A = [-int(i) for i in input().split()]
heapify(A)
while M > 0:
    heappush(A, heappop(A) / 2)
    M -= 1
print(-sum(int(i) for i in A))
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
for i in range(sum(a),-1,-2):
    s=[i/2]
    answer=[]        
    for n in range(N):
        s.append(a[n]-s[n])
        answer.append(int(2*s[n]))
    if s[N-1]+i/2==a[N-1]:
        print(*answer)
        exit(0)

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
x_1=sum(a)
for i in range(1,N,2):
    x_1-=2*(a[i])
x=[x_1]
for j in range(1,N):
    x.append(2*a[j-1]-x[j-1])
print(*x)
### BUGGY CODE ###

# coding: utf-8

from itertools import product as prod
import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f2(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1

    for i, j, d in prod(range(l), range(2), range(D)):
        maxk = 9 if j else int(K[i])
        dpij = dp[i][j]
        dpi1 = dp[i + 1]
        for k in range(maxk + 1):
            dpi1j = dpi1[j or k < maxk]
            d_ = (d + k) % D
            dpi1j[d_] += dpij[d]
            dpi1j[d_] %= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100

print(f2(K, D))


### FIXED CODE ###

# coding: utf-8

import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1
    for i in range(l):
        ki = int(K[i])
        for j in range(2):
            uki = 9 if j else ki
            dpij = dp[i][j]
            for d in range(D):
                for k in range(uki + 1):
                    dpij_ = dp[i + 1][j or k < ki]
                    d_ = (d + k) % D
                    dpij_[d_] += dpij[d]
                    dpij_[d_] %= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100

print(f(K, D))
### BUGGY CODE ###

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

result = []

for i in range(N):
    if i == 0:
        s = A[1]
        for j in range(2,N):
            s = s ^A[j]
    else:
        s = A[0]
        for j in range(1, N):
            if j != i:
                s = s ^ A[j]  
    result.append(str(s))

print(' '.join(result)) 

### FIXED CODE ###

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

result = ['' for _ in range(N)]
s = A[0]
for i in range(1,N):
    s = s ^ A[i]

for i in range(N):
    result[i] = str(s ^ A[i])

print(' '.join(result))
### BUGGY CODE ###

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

ans = 0

def dfs(sum,i,cnt):
	if i == N:
		if cnt != 0 and sum / cnt == A:
			return 1
		else:
			return 0

	return dfs(sum+L[i], i+1, cnt+1) + dfs(sum, i+1, cnt)


print(dfs(0,0,0))


### FIXED CODE ###

import sys
import numpy as np
N, A = map(int, input().split())
X = np.array(list(map(int, input().split())))
x = X - A
R = 5001
dp = np.zeros([N, R], np.int64)
dp[0][(R-1)//2] += 1
dp[0][(R-1)//2 + x[0]] += 1

for i in range(1,N):
	for j in range(R):
		if 0 <= j-x[i] <= R-1:
			dp[i][j] = dp[i-1][j] + dp[i-1][j-x[i]]
		else:
			dp[i][j] = dp[i-1][j]
print(dp[N-1][(R-1)//2]-1)
### BUGGY CODE ###

from decimal import *
getcontext().prec = 100000
a,b,c=map(int,input().split())
if Decimal(a).sqrt()+Decimal(b).sqrt()<Decimal(c).sqrt():
  print('Yes')
else:
  print('No')

### FIXED CODE ###

import math
a,b,c=map(int,input().split())
if 4*a*b<(c-a-b)*(c-a-b) and c>a+b:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

H, W, D = map(int, input().split())
A_where = [0] * (H*W+1)
A_where[0] = (-1, -1)
for p in range(H):
    A = list(map(int, input().split()))
    for q in range(W):
        A_where[A[q]] = (p, q)

Q = int(input())

DP = [[0] * (H*W+1) for _ in range(H*W+1)]

for w in range(D, H*W, D):
    for start in range(H*W+1-w):
        if start + w > H*W:
            continue
        if w == D:
            y1, x1 = A_where[start]
            y2, x2 = A_where[start + w]
            DP[start][start+w] = abs(y1-y2) + abs(x1-x2)
        else:
            DP[start][start+w] = DP[start][start+w-D] + DP[start+w-D][start+w]

for i in range(Q):
    l, r = map(int, input().split())
    print(DP[l][r])

### FIXED CODE ###

H, W, D = map(int, input().split())
A_where = [0] * (H*W+1)
A_where[0] = (-1, -1)
for p in range(H):
    A = list(map(int, input().split()))
    for q in range(W):
        A_where[A[q]] = (p, q)

Q = int(input())

DP = [0] * (H*W+1)

for i in range(D+1, H*W+1):
    y1, x1 = A_where[i]
    y2, x2 = A_where[i-D]

    DP[i] = DP[i-D] + abs(y1-y2) + abs(x1-x2)

for i in range(Q):
    l, r = map(int, input().split())
    print(DP[r] - DP[l])
### BUGGY CODE ###

N,M=map(int, input().split())
goods_value = list(map(int, input().split()))

#　貪欲法で現在の価格がもっとも大きいものから割引券を使っていけば良い
current_value=goods_value
left_discount = M
while left_discount > 0:
    maximum_value = max(current_value)
    maximum_value_index = current_value.index(maximum_value)
    current_value[maximum_value_index] = maximum_value // 2
    left_discount -= 1
    
print(sum(current_value))




### FIXED CODE ###

# 優先度付きキューとか言うものが使えるかどうかが鍵になる
# pythonでは標準でheapqが使える．要するにヒープのこと．ただしヒープでは最小値しか取り出せないのでそこに注意する必要がある.
# 計算量はO(log(N))になる
N,M = map(int,input().split())
A = list(map(int,input().split()))
# 解法 bisectとsort(最初だけ)を使う
# dequeでbisectって使えんのかなぁ？
#A.sort()
#from collections import deque
#A = deque(A)
A = [-a for a in A]
import heapq
heapq.heapify(A)
import bisect
for i in range(M):
    a = heapq.heappop(A)
    new = a/2
    # listに挿入する．ただしpythonのlistは可変長配列なので，linked-listではない.それゆえ末尾や先頭以外への要素の挿入はO(N)かかる
    #bisect.insort_left(A,new)   # やってることはA.sort(bisect.bisect_left(A,new),new)．
    heapq.heappush(A,new)
import numpy as np
A = np.array(A,dtype=np.int64)
print(-A.sum())
### BUGGY CODE ###

import statistics
from decimal import Decimal,ROUND_HALF_UP

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

for i in range(n):
    a[i] = a[i]-(i+1)
a.sort()

med = Decimal(str(statistics.median(a))).quantize(Decimal('0'), rounding=ROUND_HALF_UP)
if med == 0:
    print(sum([abs(i) for i in a]))
    exit()
    
set_a = list(set(a))
near = float('inf')
for i in range(len(set_a)):
    if abs(med - set_a[i]) < near:
        near = abs(med - set_a[i])
        mid = set_a[i]

print(sum([abs(i-mid) for i in a]))

### FIXED CODE ###

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

for i in range(n):
    a[i] -= i+1
a.sort()

ans = 0
for i in range(n):
    ans += abs(a[i] - a[n//2])
print(ans)