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

n, k = map(int, input().split())
mod = 10 ** 9 + 7
graph = {i + 1:[] for i in range(n)}
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
com = 1
check_list = [1]
count = {i + 1:0 for i in range(n)}
check = check_list.pop(0)
next_check = graph[check]
for i in range(len(next_check)):
    count[next_check[i]] += i
    check_list.append(next_check[i])
    graph[next_check[i]].remove(check)
com *= k
while check_list:
    check = check_list.pop(0)
    next_check = graph[check]
    for i in range(len(next_check)):
        count[next_check[i]] += i
        check_list.append(next_check[i])
        graph[next_check[i]].remove(check)
    if check in graph[1]:
        com *= k - 1 - count[check]
        com %= mod
    else:
        com *= k - 2 - count[check]
        com %= mod
print(com)

### FIXED CODE ###

import collections

n, k = map(int, input().split())
mod = 10 ** 9 + 7
graph = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
flag = [False for i in range(n + 1)]
flag[1] = True
queue = collections.deque([1])
ans = k
while queue:
    test = queue.popleft()
    temp = [flag[graph[test][i]] for i in range(len(graph[test]))].count(True)
    num = 0
    for i in range(len(graph[test])):
        if flag[graph[test][i]] == True:
            continue
        ans *= (k - temp - num - 1)
        ans %= mod
        num += 1
        queue.append(graph[test][i])
        flag[graph[test][i]] = True
print(ans)
### BUGGY CODE ###

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

weights = [0]*(N+10)
values = [0]*(N+10)

dp = [[0]*(W+10) for i in range(N+10)]

for i in range(N):
    weights[i], values[i] = map(int, input().split())
    for sum_w in range(W+1):
        if sum_w >= weights[i]:
            dp[i+1][sum_w] = max(dp[i][sum_w-weights[i]]+values[i],
                                 dp[i+1][sum_w])
        else:
            dp[i+1][sum_w] = max(dp[i][sum_w],
                                 dp[i+1][sum_w])

print(max([max(row) for row in dp]))

### FIXED CODE ###

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

weights = [0]*(N+5)
values = [0]*(N+5)

dp = [[0]*(W+5) for i in range(N+5)]

for i in range(N):
    weights[i], values[i] = map(int, input().split())
    for sum_w in range(W+1):
        if sum_w >= weights[i]:
            if dp[i+1][sum_w] < dp[i][sum_w-weights[i]]+values[i]:
                dp[i+1][sum_w] = dp[i][sum_w-weights[i]]+values[i]
        if dp[i+1][sum_w] < dp[i][sum_w]:
            dp[i+1][sum_w] = dp[i][sum_w]


print(max([max(row) for row in dp]))
### BUGGY CODE ###

s=input()[::-1]
l=len(s)
dp=[[0 for j in range(13)] for i in range(l)]
if s[0] == "?":
    for j in range(10):dp[0][j]=1
else:
    dp[0][int(s[0])]=1
for i in range(1,l):
    mod = 10**i % 13
    if s[i] == "?":
        for j in range(10):
            for k in range(13):
                dp[i][(k+j*mod)%13] += dp[i-1][k]
    else:
        for k in range(13):
            dp[i][(k+int(s[i])*mod)%13] += dp[i-1][k]
print(dp[-1][5]%(10**9+7))

### FIXED CODE ###

s=input()[::-1]
l=len(s)
dp=[[0 for j in range(13)] for i in range(l)]
if s[0] == "?":
    for j in range(10):dp[0][j]=1
else:
    dp[0][int(s[0])]=1
for i in range(1,l):
    mod = pow(10,i,13)
    if s[i] == "?":
        for j in range(10):
            for k in range(13):
                dp[i-1][k] %= 10**9+7
                dp[i][(k+j*mod)%13] += dp[i-1][k]
    else:
        for k in range(13):
            dp[i-1][k] %= 10**9+7
            dp[i][(k+int(s[i])*mod)%13] += dp[i-1][k]
print(dp[-1][5]%(10**9+7))
### BUGGY CODE ###

def main():
  _max = max
  s = input()
  t = input()
  slen = len(s)
  tlen = len(t)
  dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
  for i in range(slen):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    si = s[i]
    for j in range(tlen):
      j1 = j + 1
      if si == t[j]:
        dpi1[j1] = _max(dpi1[j1], dpi[j] + 1, dpi1[j], dpi[j1])
      else:
        dpi1[j1] = _max(dpi1[j1],             dpi1[j], dpi[j1])
  result = ''
  i = slen
  j = tlen
  while i > 0 and j > 0:
    if dp[i - 1][j] == dp[i][j]:
      i -= 1
    elif dp[i][j - 1] == dp[i][j]:
      j -= 1
    else:
      result = s[i - 1] + result
      i -= 1
      j -= 1
  print(result)
main()


### FIXED CODE ###

s = input()
t = input()
slen = len(s)
tlen = len(t)
dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
for i in range(slen):
  for j in range(tlen):
    if s[i] == t[j]:
      dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])
result = ''
i = slen
j = tlen
while i > 0 and j > 0:
  if dp[i - 1][j] == dp[i][j]:
    i -= 1
  elif dp[i][j - 1] == dp[i][j]:
    j -= 1
  else:
    result = s[i - 1] + result
    i -= 1
    j -= 1
print(result)
### BUGGY CODE ###

n= int(input())
cout,cout2 = 0,0
for i in range(n-1):
        cout += 1
        cout2 += cout
print(cout2)
        

### FIXED CODE ###

n= int(input()) -1
cout = (n*(2+n-1))//2
print(cout)
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
A=[a[i]^a[i-1] for i in range(0,N)]
B=[b[i]^b[i-1] for i in range(0,N)]

ca=0
for i in range(0,N):
    ca=ca|A[i]
    ca=ca<<35
ca=ca>>35
cb=0
for i in range(0,N):
    cb=cb|B[i]
    cb=cb<<35
cb=cb>>35

for k in range(0,N):
    if ca==cb:
        print(k,a[k]^b[0])
    x=0
    for i in range(0,35):
        if cb &1==1:
            x+=pow(2,i)
        cb=cb>>1
    x=x<<35*(N-1)
    cb=cb|x


### FIXED CODE ###

def divisors(M):#Mの約数列 O(n^(0.5+e))
    import math
    d=[]
    i=1
    while math.sqrt(M)>=i:
        if M%i==0:
            d.append(i)
            if i**2!=M:
                d.append(M//i)
        i=i+1
    d.sort()
    return d

import numpy as np
N=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
A=np.array([a[i]^a[i-1] for i in range(0,N)])
B=np.array([b[i]^b[i-1] for i in range(0,N)])
d=divisors(N)
perioda=N
for i in range(0,len(d)):
    test=np.roll(A,-d[i])
    if all(test==A):
        perioda=min(perioda,d[i])

periodb=N
for i in range(0,len(d)):
    test=np.roll(B,-d[i])
    if all(test==B):
        periodb=min(periodb,d[i])

if perioda==periodb:
    A=A[:perioda]
    B=B[:periodb]
    kouho=[]
    for i in range(0,len(B)):
        if A[i]==B[0]:
            kouho.append(i)
    ans=-1
    for i in range(0,len(kouho)):
        test=np.roll(A,-kouho[i])
        if all(test==B):
            ans=kouho[i]
            break
    if ans!=-1:
        for i in range(0,N//perioda):
            print(ans+perioda*i,a[ans+perioda*i]^b[0])
### BUGGY CODE ###

H,W,D=list(map(int,input().split()))
arr=[0 for i in range(H*W+1)]
for y in range(H):
    for x,n in enumerate(map(int,input().split())):
        arr[n]=[x,y]

dic={}

Q=int(input())
for i in range(Q):
    ans=0
    now,goal= list(map(int,input().split()))
    nx=arr[now][0]
    ny=arr[now][1]
    tmp=now
    for j in range((goal-now)//D):
        if dic.get(tmp*H*W+goal,0)!=0:
            dic[now*H*W+goal]=ans+dic[tmp*H*W+goal]
            break
        tmp+=D
        x=arr[tmp][0]
        y=arr[tmp][1]
        ans+=abs(x-nx)+abs(y-ny)
        nx=x
        ny=y
        dic[now*H*W+tmp]=ans
    print(dic.get(now*H*W+goal,0))

### FIXED CODE ###

H,W,D=list(map(int,input().split()))
map_=[[0,0] for _ in range(H*W+1)]
for y in range(H):
    for x,A in enumerate(map(int,input().split())):
        map_[A]=[x+1,y+1]

cost=[0 for _ in range(H*W+1)]
for i in range(D+1,H*W+1):
    cost[i]+=abs(map_[i][0]-map_[i-D][0])+abs(map_[i][1]-map_[i-D][1])+cost[i-D]
Q=int(input())
for i in range(Q):
    L,R=list(map(int,input().split()))
    print(cost[R]-cost[L])
### BUGGY CODE ###

from heapq import heappop,heappush,heapify
from collections import deque
N, M = map(int, input().split())
A = [int (i) for i in input().split()]
heapify(A)
D = []
P = 0
for i in range(M):
  B,C = map(int, input().split())
  D.extend([C]*B)
  P += B
D.sort(reverse=True)
for i in range(P):
  if A[0] < D[i]:
    x = heappop(A)
    heappush(A,D[i])
  else:
    break
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = [int(i) for i in input().split()]
table = []
for i in range(N):
  table.append((A[i],1))
for i in range(M):
  b,c = map(int, input().split())
  table.append((c,b))
table.sort()
count = 0
ans = 0
while True:
  c, b = table.pop()
  if b <= N - count:
    ans += c*b
    count += b
  else:
    ans += (N-count)*c
    break
print(ans)
### BUGGY CODE ###

def main():
    n, p = map(int, input().split())
    if n == 1:
        print(p)
    else:
        ans = 1
        cnt = 0
        while p % 2 == 0:
            p //= 2
            cnt += 1
        if cnt >= n:
            ans *= 2**(cnt//n)
        for i in range(3, p+1, 2):
            if i**n > p:
                break
            cnt = 0
            while p % i == 0:
                p //= i
                cnt += 1
            if cnt >= n:
                ans *= i**(cnt//n)
        print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from math import log
def main():
    n, p = map(int, input().split())
    if n == 1:
        print(p)
    else:
        ans = 1
        if n > int(log(p, 2))+2:
            print("1")
            sys.exit()
        if p % (2**n) == 0:
            while p % (2**n) == 0:
                ans *= 2
                p //= (2**n)
        for i in range(3, 10**6+1, 2):
            while p % (i**n) == 0:
                ans *= i
                p //= (i**n)
        print(ans)

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

# import copy
import sys
import numpy as np
imput = sys.stdin.readline
def main():
    N, W = map(int, input().split())
    dp = np.zeros((N+1, W+1))
    for i in range(1, N+1):
        w, v = map(int, input().split())
        for j in range(1, W+1):
            if j<w:
                dp[i, j] = dp[i-1, j]
            else:
                dp[i, j] = max(dp[i-1, j], dp[i-1, j-w]+v)
    # print(dp)
    print(int(dp[i, j]))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
imput = sys.stdin.readline
def main():
    N, W = map(int, input().split())
    dp = [[0]*(W+1) for _ in range(N+2)]
    for i in range(1, N+1):
        w, v = map(int, input().split())
        for j in range(1, W+1):
            if j<w:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)
    print(int(dp[i][j]))


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

import sys
import numpy as np

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, M = rl()
A = np.array(rl())
A_cum = A.cumsum()
A_cum %= M
answer = 0

for i in range(N):
    answer += (A_cum[i:] == 0).sum()
    A_cum -= A_cum[i]

print(answer)
#13

### FIXED CODE ###

import sys
import numpy as np
from collections import Counter
from math import factorial

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, M = rl()
A = np.array(rl())
A_cum = A.cumsum()
A_cum %= M
A_cum = A_cum.tolist()
c = Counter(A_cum)
answer = 0

for k, v in c.items():
    if k == 0:
        answer += v
    if v >= 2:
        answer += factorial(v) // factorial(2) // factorial(v-2)

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

def main():
    N, P = list(map(int, input().split()))
    S = map(int, input())
    K = {}
    r = 0
    for i in S:
        L = {}
        L[i % P] = 1
        for j, k in K.items():
            p = (j * 10 + i) % P
            L[p] = L.get(p, 0) + k
        r += L.get(0, 0)
        K = L
    return r
   

print(main())


### FIXED CODE ###

def main():
    N, P = list(map(int, input().split()))
    S = map(int, input())
    if P == 2 or P == 5:
        r = 0
        for i, s in enumerate(S):
            if s % P == 0:
                r += (i + 1)
        return r

    g1 = [1, 1]
    g2 = [1, 1]
    inverse = [0, 1]
    mod = P
    for i in range(2, P):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod // i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)

    H = [0] * N
    h = 0
    for i, s in enumerate(S):
        h = (h * 10 + s) % P
        H[i] = h
    K = [0] * P
    K[0] = 1
    shift = 1
    r = 0
    for i, h in enumerate(H):
        t = (h * inverse[shift]) % P
        r += K[t]
        K[(h * inverse[shift]) % P] += 1
        shift = (shift * 10) % P

    return r
   

print(main())
### BUGGY CODE ###

import math
N = int(input())

def search(n):
    global N
    for x in range(1, int(math.sqrt(N)) + 1):
        if n - x*x <= 0:
            return None
        for y in range(1, int(math.sqrt(N)) + 1):
            if n - x*x - y*y - x*y <= 0:
                break
            z = binarySearch(n, x, y)
            if z:
                return (x, y, z)


def binarySearch(n, x, y):
    global N
    right = -1
    left = N + 1
    while(abs(right - left) > 1):
        z = left + (right - left) // 2
        l = x*x + y*y + z*z + x*y + y*z + z*x
        if l == n:
            return z
        elif l < n:
            right = z
        else:
            left = z
        # print(right, left, z)
    return None

for n in range(1, N+1):
    ans = search(n)
    if ans == None:
        print(0)
        continue
    ans = len(set(ans))
    if ans == 1:
        print(1)
    elif ans == 2:
        print(3)
    else:
        print(6)

### FIXED CODE ###

N = int(input())
ans = [0]*10010

for x in range(1, 105):
    for y in range(1, 105):
        for z in range(1, 105):
            v = x*x + y*y + z*z + x*y + y*z + z*x
            if v <= 10005:
                ans[v] += 1
for i in range(1, N+1):
    print(ans[i])
### BUGGY CODE ###

s = input()
K = int(input())

ret = ''
for i, c in enumerate(s) :
    if i == len(s) - 1 :
        K %= 26
        if ord(c) + K > 122 :
            ret += chr(ord(c) + K - 26)
        else :
            ret += chr(ord(c) + K)
    
    elif ord(c) + K > 122 :
        ret += 'a'
        K -= 123 - ord(c)
    else :
        ret += c
        
print(ret)

### FIXED CODE ###

s = [ord(i) for i in input()]
K = int(input())

ret = []
for c in s[:-1] :
    if c == 97 :
        ret.append('a')
        continue
        
    if c + K > 122 :
        ret.append('a')
        K -= 123 - c
    else :
        ret.append(chr(c))
        
K %= 26
ret.append(chr((s[-1] + K - 97) % 26 + 97))
        
print(''.join(ret))
### BUGGY CODE ###

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

def a(x):
    return abs(x - k)

if n > k:
    tmp = k
    while not (n - tmp) % k == 0:
        tmp -= 1
    n = tmp

while True:
    tmp = n
    n = a(n)
    if tmp < n:
        print(tmp)
        break


### FIXED CODE ###

n, k = [int(i) for i in input().split()]
print(min(n % k, k - n % k))
### BUGGY CODE ###

S = input()
div = 10**9 + 7

lenS = len(S)
dp = [[0]*13 for _ in range(lenS+1)]

ini = S[0]
if ini=='?':
    for i in range(10):
        dp[1][i] = 1
else:
    dp[1][int(ini)] = 1

for i in range(2, lenS+1):
    chara = S[i-1]
    if chara=='?':
        for d in range(13):
            for e in range(10):
                newd = (d*10+e)%13
                dp[i][newd] = (dp[i][newd]+dp[i-1][d])%div
    else:
        for d in range(13):
            newd = (d*10+int(chara))%13
            dp[i][newd] = (dp[i][newd]+dp[i-1][d])%div

print(dp[-1][5])


### FIXED CODE ###

S = input()
div = 10**9 + 7

lenS = len(S)
dp = [[0]*13 for _ in range(lenS+1)]

ini = S[0]
if ini=='?':
    for i in range(10):
        dp[1][i] = 1
else:
    dp[1][int(ini)] = 1

for i in range(2, lenS+1):
    chara = S[i-1]
    if chara=='?':
        for d in range(13):
            for e in range(10):
                newd = (d*10+e)%13
                dp[i][newd] = (dp[i][newd]+dp[i-1][d])%div
    else:
        for d in range(13):
            newd = (d*10+int(chara))%13
            dp[i][newd] = (dp[i][newd]+dp[i-1][d])%div

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

a = int(input())
c = 0
for i in range(a):
  c +=i
print(c)

### FIXED CODE ###

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

N, M = map(int, input().split())
ab = []
d = [0 for _ in range(M)]
for i in range(M):
  ab.append(list(map(int, input().split())))
  for k in list(map(int, input().split())):
    d[i] += 2**(k-1)
  
infty = 10**8
  
dp = [infty for j in range(2**N)]
#i番目の鍵まで使って状態jにできる最小のコスト
dp[0] = 0

for i in range(M):
  for j in range(2**N):
    dp[j | d[i]] = min(dp[j | d[i]], dp[j] + ab[i][0])

ans = dp[2**N-1] if dp[2**N-1] != infty else -1
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
ab = []
d = [0 for _ in range(M)]
for i in range(M):
  ab.append(list(map(int, input().split())))
  for k in list(map(int, input().split())):
    d[i] += 2**(k-1)
  
infty = 10**8
  
dp = [infty for j in range(2**N)]
#i番目の鍵まで使って状態jにできる最小のコスト
dp[0] = 0

for i in range(M):
  for j in range(2**N):
    if dp[j|d[i]] > dp[j] + ab[i][0]:
      dp[j | d[i]] =  dp[j] + ab[i][0]

ans = dp[2**N-1] if dp[2**N-1] != infty else -1
print(ans)
### BUGGY CODE ###

import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, Ma, Mb = map(int, input().split())
A = [0] * N
B = [0] * N
C = [0] * N

for i in range(N):
    A[i], B[i], C[i] = map(int, input().split())

INF = 1 << 50
LEN = 500
dp = [[INF] * (LEN + 1) for _ in range(LEN + 1)]
dp[0][0] = 0

for i in range(N):
    for j in range(LEN, A[i] - 1, -1):
        for k in range(LEN, B[i] - 1, -1):
            dp[j][k] = min(dp[j][k], dp[j - A[i]][k - B[i]] + C[i])

cnt = 1
ans = INF
while cnt * Ma < LEN and cnt * Mb < LEN:
    ans = min(ans, dp[cnt * Ma][cnt * Mb])
    cnt += 1

print(ans if ans != INF else -1)

### FIXED CODE ###

import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, Ma, Mb = map(int, input().split())
A = [0] * N
B = [0] * N
C = [0] * N

for i in range(N):
    A[i], B[i], C[i] = map(int, input().split())

INF = 1 << 50
LEN = 500
dp = [[INF] * (LEN + 1) for _ in range(LEN + 1)]
dp[0][0] = 0

for i in range(N):
    for j in range(LEN, A[i] - 1, -1):
        for k in range(LEN, B[i] - 1, -1):
            dp[j][k] = min(dp[j][k], dp[j - A[i]][k - B[i]] + C[i])

cnt = 1
ans = INF
while cnt * Ma < LEN and cnt * Mb < LEN:
    ans = min(ans, dp[cnt * Ma][cnt * Mb])
    cnt += 1

print(ans if ans != INF else -1)
### BUGGY CODE ###

N=int(input())
X=[]
x=[]
for i in range(N):
    a,b=map(int,list(input().split(" ")))
    X.append(a+b)
    x.append(a-b)

def nibun(lis,x):
    i=len(lis)
    if i==1:
        if lis[0]<=x:
            return lis[0]
    elif lis[i//2]==x:
        return x
    else:
        if x<lis[i//2]:
            return nibun(lis[:i//2],x)
        else:
            return nibun(lis[i//2:],x)

X.sort()
x.sort()
a={}
a[x[0]]=0
a[X[0]]=1
for i in range(1,N):
    k=nibun(X[:i],x[i])
    if k==None:
        a[x[i]]=0
    else:
        a[x[i]]=a[k]
    a[X[i]]=max(a[X[i-1]],a[x[i]]+1)
print(a[X[N-1]])

### FIXED CODE ###

N=int(input())
X=[]
for i in range(N):
    a,b=map(int,list(input().split(" ")))
    X.append([a+b,a-b])
X.sort()
D={}
D[0]=1
exe=[0]
for i in range(1,N):
    k=X[i][0]
    if X[i][1]<X[exe[-1]][0]:
        D[i]=D[exe[-1]]
    else:
        D[i]=D[exe[-1]]+1
        exe.append(i)
print(len(exe))
### BUGGY CODE ###

import sys
from collections import deque
readline = sys.stdin.readline

N = int(readline())
P = list(map(int, readline().split()))

geta = N+2
G = [0]*(geta*geta)

for v in range(-1-(-N//2), -1, -1):
    l = v+1
    r = N-v
    for i in range(geta):
        G[i*geta+l] = v
        G[i*geta+r] = v
        G[l*geta+i] = v
        G[r*geta+i] = v

for i in range(geta):
    G[i*geta] = -1
    G[i*geta + geta-1] = -1
    G[i] = -1
    G[geta*(geta-1)+i] = -1

Pn = []

for p in P:
    a, b = divmod(p-1, N)
    Pn.append((1+a)*geta+1+b)

DIREC = [1, -1, geta, -geta]
ans = 0
used = [False]*(geta*geta)
for p in Pn:
    ans += G[p]
    res = G[p]
    for d in DIREC:
        res = min(res, G[p+d])
    if G[p] != res:
        G[p] = res
        Q = deque([p])
        while Q:
            vn = Q.pop()
            for d in DIREC:
                vf = vn + d
                if not used[vf]:
                    if G[vf] > G[vn] + 1:
                        G[vf] = G[vn] + 1
                        Q.appendleft(vf)
                else:
                    if G[vf] > G[vn]:
                        G[vf] = G[vn]
                        Q.appendleft(vf)
                    
    used[p] = True
print(ans)

### FIXED CODE ###

import sys
from collections import deque
readline = sys.stdin.readline

N = int(readline())
P = list(map(int, readline().split()))

geta = N+2
G = [0]*(geta*geta)

for v in range(-1-(-N//2), -1, -1):
    l = v+1
    r = N-v
    for i in range(geta):
        G[i*geta+l] = v
        G[i*geta+r] = v
        G[l*geta+i] = v
        G[r*geta+i] = v

for i in range(geta):
    G[i*geta] = -1
    G[i*geta + geta-1] = -1
    G[i] = -1
    G[geta*(geta-1)+i] = -1

Pn = []

for p in P:
    a, b = divmod(p-1, N)
    Pn.append((1+a)*geta+1+b)

DIREC = (1, -1, geta, -geta)
ans = 0
used = [False]*(geta*geta)
for p in Pn:
    ans += G[p]
    res = G[p]
    for d in DIREC:
        res = min(res, G[p+d])
    if G[p] != res:
        G[p] = res
        Q = [p]
        while Q:
            vn = Q.pop()
            for d in DIREC:
                vf = vn + d
                if not used[vf]:
                    if G[vf] > G[vn] + 1:
                        G[vf] = G[vn] + 1
                        Q.append(vf)
                else:
                    if G[vf] > G[vn]:
                        G[vf] = G[vn]
                        Q.append(vf)
                    
    used[p] = True
print(ans)
### BUGGY CODE ###

k, s = map(int, input().split())
ks = [_ for _ in range(k+1)]

count = 0

for ksk1 in ks:
    for ksk2 in ks:
        for ksk3 in ks:
            if s == ksk1 + ksk2 + ksk3:
                count += 1
            
print(count)

### FIXED CODE ###

k, s = map(int, input().split())
ks = [_ for _ in range(k+1)]

count = 0

for ksk1 in ks:
    for ksk2 in ks:
        z = s - ksk1 - ksk2
        if 0 <= z <= k:
            count += 1
            
print(count)