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

mod = 10 ** 9 + 7
def main():
    n, k = map(int,input().split())
    lis = [i for i in range(n + 1)]
    res = 0
    for i in range(k, n + 2):
        res += (sum(lis[-i:]) - sum(lis[:i]) + 1)
        res %= mod
    print(res)
if __name__ == '__main__':
    main()


### FIXED CODE ###

mod = 10 ** 9 + 7
def main():
    n, k = map(int,input().split())
    res = 0
    for i in range(k, n + 2):
        mis = i *(i-1)//2
        mas = n*(n+1)//2 - (n-i)*(n-i+1)//2
        res += mas - mis +1
        res %= mod
    print(res)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

N = int(input())
A = [list(reversed(list(map(lambda x:int(x)-1,input().split())))) for i in range(N)]
B = {i:row for i,row in enumerate(A)}

k = 0
end = 0
while 1:
    used = set()
    dels = []
    for i,q in B.items():
        if not q: continue
        if i in used: continue
        j = q[-1]
        if j in used: continue
        if A[j][-1] == i:
            A[j].pop()
            A[i].pop()
            used.add(i)
            used.add(j)
            if not A[i]:
                end += 1
                dels.append(i)
            if not A[j]:
                end += 1
                dels.append(j)
    if not used:
        print(-1)
        exit()
    if end == N:
        print(k+1)
        exit()
    for i in dels:
        del B[i]
    k += 1

### FIXED CODE ###

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

N = int(input())
A = [list(reversed(list(map(lambda x:int(x)-1,input().split())))) for i in range(N)]
B = {i:row for i,row in enumerate(A)}

end = 0
for k in range(8000):
    used = set()
    dels = []
    for i,q in B.items():
        if not q: continue
        if i in used: continue
        j = q[-1]
        if j in used: continue
        if A[j][-1] == i:
            A[j].pop()
            A[i].pop()
            used.add(i)
            used.add(j)
            if not A[i]:
                end += 1
                dels.append(i)
            if not A[j]:
                end += 1
                dels.append(j)
    if not used:
        print(-1)
        exit()
    if end == N:
        print(k+1)
        exit()
    for i in dels:
        del B[i]

print(N*(N-1)//2)
### BUGGY CODE ###

import math as m
a,b=map(int,input().split())
print(m.factorial(a)*m.factorial(b)*[1,2][a==b] if -2<a-b<2 else 0)

### FIXED CODE ###

m=1000000007
f=lambda j,k:(j%m)*(k%m)%m
a,b=sorted(map(int,input().split()))
x=1
for i in range(2,a+1):
  x=f(x,i)
print(f(f(x,[x*b,x][a==b]),[1,2][a==b]) if b-a<2 else 0)
### BUGGY CODE ###

n=int(input())
a=input().split()
LS=""
RS=""
if n%2==0:
    for i in range(n):
        if i==0:
            RS+=a[0]
        elif i==1:
            LS+=a[1]
        elif i%2==0:
            RS=RS+" "+a[i]
        else:
            LS=a[i]+" "+LS
else:
    for i in range(n):
        if i==0:
            LS+=a[0]
        elif i==1:
            RS+=a[1]
        elif i%2==1:
            RS=RS+" "+a[i]
        else:
            LS=a[i]+" "+LS
print(LS,RS)


### FIXED CODE ###

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

l=a[0:n:2]
r=a[1:n:2]
if n%2==1:
    print(*l[::-1],*r)
else:
    print(*r[::-1],*l)
### BUGGY CODE ###

n=int(input())
g = [[]for i in range(n)]
ab = [list(map(int,input().split()))for i in range(n-1)]
for i in range(n-1):
    g[ab[i][0]-1].append(ab[i][1]-1)
ans = [[-1 for i in range(n)]for j in range(n)]
banColor = [-1]*n
from queue import deque
q = deque([])
q.append(0)
ma = 0
while q:
    nord = q.popleft()
    offset = 0
    for idx,value in enumerate(g[nord]):
        if idx ==banColor[nord]:
            offset += 1
        ans[nord][value] = idx + offset
        banColor[value] = idx+offset
        q.append(value)
        ma = max(ma,idx+offset+1)
print(ma)
for i in range(n-1):
    print(ans[ab[i][0]-1][ab[i][1]-1]+1)

### FIXED CODE ###

from queue import deque

n=int(input())
ab = [list(map(int,input().split()))for i in range(n-1)]
g = [[]for i in range(n)]
for i,j in ab:
    g[i-1].append(j-1)
ans = {}
banColor = [-1]*n

q = deque([])
q.append(0)
ma = 0

while q:
    nord = q.popleft()
    offset = 0
    for idx,value in enumerate(g[nord]):
        if idx ==banColor[nord]:
            offset += 1
        ans[(nord,value)]= idx + offset
        banColor[value] = idx+offset
        q.append(value)
        ma = max(ma,idx+offset+1)
print(ma)
for i,j in ab:
    print(ans[(i-1,j-1)]+1)
### BUGGY CODE ###

N, M  = map(int, input().split(" "))
Alist = list(map(int, input().split(" ")))
Alist.sort()
ans = 0
#print(Alist)
for i in range(M):
    b, c = map(int, input().split(" "))
    for j in range(b):
        if Alist[j] < c:
            Alist[j] = c
        else:
            break
    Alist.sort()

for k in range(N):
    ans += Alist[k]

print(ans)

### FIXED CODE ###

N, M  = map(int, input().split(" "))
Alist = list(map(int, input().split(" ")))
bclist = []
leng = len(Alist)
ans = 0
#print(Alist)
for i in range(M):
    b, c = (map(int, input().split(" ")))
    bclist.append([c,b])
bclist.sort(reverse = True)
#print(bclist)

count = 0
for j in range(M):
    for n in range(bclist[j][1]):
        Alist.append(bclist[j][0])
    count += bclist[j][1]
    if count >= leng:
        break
    

Alist.sort()

for k in range(leng):
    ans += Alist[-k-1]

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

n=int(input())
if all(n%i for i in range(2,int(n**.5)+1)):
	print(len(str(n)))
	exit()
for i in range(int(0-n**.5//-1),n+1):
	if n%i==0:
		print(len(str(i)))
		exit()

### FIXED CODE ###

n=int(input())
for i in range(int(0-n**.5//-1),1,-1):
	if n%i==0:
		print(len(str(n//i)))
		exit()
print(len(str(n)))
### BUGGY CODE ###

S = input()
T = input()

dp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]
for i in range(1, len(S) + 1):
    for j in range(1, len(T) + 1):
        indicator = 1 if S[i - 1] == T[j - 1] else 0
        dp[i][j] = max(dp[i - 1][j - 1] + indicator, dp[i - 1][j], dp[i][j - 1])

ans = ''


def print_lcs(s, t, dp_table, i, j):
    global ans
    if i == 0 or j == 0:
        return
    if S[i - 1] == T[j - 1]:
        print_lcs(s, t, dp, i - 1, j - 1)
        ans += S[i - 1]
    else:
        if dp[i - 1][j] >= dp[i][j - 1]:
            print_lcs(S, T, dp, i - 1, j)
        else:
            print_lcs(S, T, dp, i, j - 1)


print_lcs(S, T, dp, len(S), len(T))
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
S = input()
T = input()

dp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]
for i in range(1, len(S) + 1):
    for j in range(1, len(T) + 1):
        indicator = 1 if S[i - 1] == T[j - 1] else 0
        dp[i][j] = max(dp[i - 1][j - 1] + indicator, dp[i - 1][j], dp[i][j - 1])

ans = ''


def print_lcs(s, t, dp_table, i, j):
    global ans
    if i == 0 or j == 0:
        return
    if S[i - 1] == T[j - 1]:
        print_lcs(s, t, dp, i - 1, j - 1)
        ans += S[i - 1]
    else:
        if dp[i - 1][j] >= dp[i][j - 1]:
            print_lcs(S, T, dp, i - 1, j)
        else:
            print_lcs(S, T, dp, i, j - 1)


print_lcs(S, T, dp, len(S), len(T))
print(ans)
### BUGGY CODE ###

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

b=sorted(list(map(int,input().split())))
c=sorted(list(map(int,input().split())))
#print(a)
#print(b)
#print(c)
c_count=[]#cから行けるところの回数
b_count=[]#bから行けるところの回数

j=0
count=0
for i in range(n):#cから行けるところの回数
    for j in range(count,n):
        if b[j]<c[i]:
            count+=1
    c_count.append(count)

count=0

for i in range(n):#bから行けるところの回数
    for j in range(count,n):
        if a[j]<b[i]:
            count+=1
    b_count.append(count)

ans=0

for i in range(n):
    ans+=sum(b_count[0:c_count[i]])

print(ans)

#print(b_count)
#print(c_count)


### FIXED CODE ###

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

b=sorted(list(map(int,input().split())))
c=sorted(list(map(int,input().split())))
#print(a)
#print(b)
#print(c)
c_count=[]#cから行けるところの回数
b_count=[]#bから行けるところの回数

j=0
count=0
for i in range(n):#cから行けるところの回数
    for j in range(count,n):
        
        if b[j]<c[i]:
 #           print("dfghj")
            count+=1
        else:
  #          print("GHJK")
            break
    c_count.append(count)

count=0

for i in range(n):#bから行けるところの回数
    for j in range(count,n):
        if a[j]<b[i]:
            count+=1
        else:
            break
    b_count.append(count)

ans=0
#print(b_count)
#print(c_count)
for i in range(1,n):
    b_count[i]+=b_count[i-1]
#print(b_count)

for i in range(n):
    if 0<=c_count[i]-1:
        ans+=b_count[c_count[i]-1]

print(ans)

#print(b_count)
#print(c_count)
### BUGGY CODE ###

from collections import deque

q = deque()
H, W = map(int, input().split())
dists = [[-1] * W for _ in range(H)]
for i in range(H):
    for j, v in enumerate(input()):
        if v == "#":
            q.append((0, i, j))

while len(q):
    d, i, j = q.popleft()
    if not 0 <= i < H or not 0 <= j < W or dists[i][j] != -1:
        continue
    dists[i][j] = d
    q.append((d+1, i-1, j))
    q.append((d+1, i+1, j))
    q.append((d+1, i, j-1))
    q.append((d+1, i, j+1))

ans = max(map(max, dists))
print(ans)
# very slow
# ans = max(sum(dists, []))
# print(ans)


### FIXED CODE ###

from time import time
from collections import deque

# reduce q.append()
# (constant-factor optimization)


def append(d, i, j):
    if not 0 <= i < H or not 0 <= j < W or dists[i][j] != -1:
        return
    dists[i][j] = d
    q.append((d, i, j))


q = deque()
H, W = map(int, input().split())
dists = [[-1] * W for _ in range(H)]
for i in range(H):
    for j, v in enumerate(input()):
        if v == "#":
            append(0, i, j)

while len(q):
    d, i, j = q.popleft()
    append(d+1, i-1, j)
    append(d+1, i+1, j)
    append(d+1, i, j-1)
    append(d+1, i, j+1)

# fast (0.01s)
ans = max(map(max, dists))
# very slow (4.2s)
# ans = max(sum(dists, []))

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

mod=10**9+7
fact=[1]
for i in range(1,5*10**5+1):
  fact.append((fact[-1]*i)%mod)
revfact=[1]
for i in range(1,5*10**5+1):
  revfact.append(pow(fact[i],mod-2,mod))
n,m=map(int,input().split())
patternA=(fact[m]*revfact[n]*revfact[m-n]*fact[n])%mod
patternB=patternA
for i in range(1,n+1):
  tmp=(fact[n]*revfact[i]*revfact[n-i])*(fact[m-i]*revfact[n-i]*revfact[m-n])*fact[n-i]
  if i%2==0:
    patternB+=tmp
    patternB%=mod
  else:
    patternB-=tmp
    patternB%=mod
print((patternA*patternB)%mod)


### FIXED CODE ###

mod=10**9+7
fact=[1]
for i in range(1,5*10**5+1):
  fact.append((fact[-1]*i)%mod)
revfact=[1]
for i in range(1,5*10**5+1):
  revfact.append(pow(fact[i],mod-2,mod))
n,m=map(int,input().split())
patternA=(fact[m]*revfact[n]*revfact[m-n]*fact[n])%mod
patternB=patternA
for i in range(1,n+1):
  tmp=(fact[n]*revfact[i]*revfact[n-i])*(fact[m-i]*revfact[n-i]*revfact[m-n])*fact[n-i]
  if i%2==0:
    patternB+=tmp
    patternB%=mod
  else:
    patternB-=tmp
    patternB%=mod
print((patternA*patternB)%mod)
### BUGGY CODE ###

#input
S = str(input())[::-1]

#output
from collections import Counter
#2019 = 3 * 673
N = len(S)
#上からi桁目までの数を決めた時2019の個数をdp[i]とする。
dp = [0] * (N)
dp[0] = int(S[0])
for i in range(N-1):
    dp[i+1] = (dp[i] + int(S[i+1]) * 10**(i+1)) % 2019

T = Counter(dp)

answer = T[0]

for t in T.values():
    answer += t*(t-1)//2

print(answer)

### FIXED CODE ###

#input
S = str(input())[::-1]

#output
from collections import Counter
#2019 = 3 * 673
N = len(S)
#上からi桁目までの数を決めた時2019の個数をdp[i]とする。
dp = [0] * (N)
dp[0] = int(S[0])
times =10
for i in range(N-1):
    dp[i+1] = dp[i] + times * int(S[i+1])
    dp[i+1] %= 2019
    times *= 10
    times %= 2019

T = Counter(dp)

answer = T[0]

for t in T.values():
    answer += t*(t-1)//2

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

# -*- coding: utf-8 -*-
a, b = map(int, input().split())
c = list(map(int, input().split()))
d = [(i + 1) / 2 for i in c]
e = sum(d[:b])
for i in range(a - b + 1):
	f = sum(d[i:b + i])
	if f > e:
		e = f
print(e)

### FIXED CODE ###

# -*- coding: utf-8 -*-
a, b = map(int, input().split())
c = list(map(int, input().split()))
d = [(i + 1) / 2 for i in c]
e = sum(d[:b])
f = e
for i in range(a - b):
	f -= d[i]
	f += d[i + b]
	if f > e:
		e = f
print(e)
### BUGGY CODE ###

import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits


def input(): return sys.stdin.readline().strip()


def INT(): return int(input())


def MAP(): return map(int, input().split())


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


sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, Q = MAP()
S = input()
lr = [LIST() for _ in range(Q)]


def func(s, l, r):
    lis = []
    ret = 0
    for i in range(l-1, r):
        lis.append(s[i])

    for i, x in enumerate(lis):
        if(i == r-l):
            break
        else:
            if x == 'A' and lis[i + 1] == 'C':
                ret += 1

    return ret


for i in range(Q):
    print(func(S, lr[i][0], lr[i][1]))


### FIXED CODE ###

import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits


def input(): return sys.stdin.readline().strip()


def INT(): return int(input())


def MAP(): return map(int, input().split())


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


sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, Q = MAP()
S = list(input())
lr = [LIST() for _ in range(Q)]

lis = [0]*N

for i, x in enumerate(S):
    if (i == N-1):
        break
    else:
        if x == 'A' and S[i + 1] == 'C':
            lis[i+1] = lis[i]+1
        else:
            lis[i+1] = lis[i]


for i in range(Q):
    print(lis[lr[i][1]-1]-lis[lr[i][0]-1])
### BUGGY CODE ###


def main()->None:
    A, B, K = map(int, input().split())
    range_K = range(K)
    
    for k in range_K:
        if A >= 1:
            A -= 1
        elif B >= 1:
            B -= 1
        if A == 0 and B == 0:
            continue

    print(A, B)





if __name__ == "__main__":
    main()

### FIXED CODE ###


def main()->None:
    A, B, K = map(int, input().split())

    if A > K:
        print(A-K, B)
    else:
        diff = K - A
        if diff < B:
            print(0, B-diff)
        else:
            print(0, 0)





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

n, k, q = map(int, input().split())
a = [int(input()) for _ in range(q)]
sc = [k] * n

for i in a:
    sc = [j - 1 for j in sc]
    sc[i - 1]+=1
for j in sc:
    print('Yes' if j > 0 else 'No')

### FIXED CODE ###

n, k, q = map(int, input().split())
sc = [k - q] * n

for i in range(q):
    sc[int(input()) - 1] += 1

for j in sc:
    print('Yes' if j > 0 else 'No')
### BUGGY CODE ###

while True:
    n=input()
    if n==0:
        break
    dp=[[0 for i in range(n)]for j in range(n)]
    flag0=0
    for i in range(n):
        j=0
        for c in raw_input():
            if c == ".":
                dp[i][j]=1
                flag0=1
            j+=1
    if flag0==0:
        print 0
    else:
        solve=1
        while True:
            flag=0
            for y in xrange(n-1):
                for x in xrange(n-1):
                    if dp[y][x]!=0:
                        old = dp[y][x]
                        dp[y][x]=min(dp[y+1][x],dp[y][x+1],dp[y+1][x+1])+1
                        if old!=dp[y][x]:
                            flag=1
            if flag==0:
                break
            solve+=1
        print solve

### FIXED CODE ###

while True:
    n=input()
    if n==0:
        break
    dp=[[0 for i in range(n+1)]for j in range(n+1)]
    for i in range(1,n+1):
        j=0
        line=" "+raw_input()
        for c in line:
            if c == ".":
                dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
            j+=1
    allmax=0
    for i in range(n+1):
        if allmax<max(dp[i]):
            allmax=max(dp[i])
    print allmax
### BUGGY CODE ###

n = int(input())
L = list(map(int, input().split()))
ret = 1
for i in L:
    ret *= i
if ret > 10**18:
    print(-1)
else:
    print(ret)

### FIXED CODE ###

n = int(input())
L = sorted(list(map(int, input().split())), reverse=True)
ret = 1
if L[-1] == 0:
    print(0)
else:
    for i in L:
        ret *= i
        if ret > 10**18:
            ret = -1
            break
    print(ret)
### BUGGY CODE ###

from itertools import accumulate

n, k = map(int, input().split())
a = list(map(int, input().split()))
for _ in range(k):
   b = [0] * n
   for i in range(n):
      b[max(0, i-a[i])] += 1
      tmp = i + a[i] + 1
      if tmp < n:
         b[tmp] -= 1
   a = list(accumulate(b))
   if a == [n] * n:
      break

print(*a)


### FIXED CODE ###

from itertools import accumulate

n, k = map(int, input().split())
a = list(map(int, input().split()))
for _ in range(k):
   b = [0] * n
   for i in range(n):
      b[max(0, i-a[i])] += 1
      tmp = i + a[i] + 1
      if tmp < n:
         b[tmp] -= 1
   a = list(accumulate(b))
   if a == [n] * n:
      break

print(*a)
### BUGGY CODE ###

import numpy as np
 
def prime(n):
    primes = np.zeros(n + 1, dtype=np.bool)
    primes[2] = 1
    primes[3::2] = 1
    for p in range(3, n + 1, 2):
        if primes[p]:
            primes[p * p::2 * p] = 0
    return primes
pp=prime(10**3)
p=[]
for i in range(2,1001):
  if pp[i]:
    p.append(i)
n=int(input())
a=list(map(int,input().split()))
def gcd(x,y):
  while y:
    x,y=y,x%y
  return x

g=a[0]
for i in a[1:]:
  g=gcd(g,i)
if g==1:
  mm=[0 for i in range(10**6+1)]
  f=True
  for i in a:
    if mm[i] and i!=1:
      f=False
      break
    mm[i]=1
    for j in range(168):
      if i%p[j]==0:
        if mm[p[j]] and i!=p[j]:
          f=False
          break
        mm[p[j]]=1
        if mm[i//p[j]] and i//p[j]!=p[j] and i!=p[j]:
          f=False
          break
        mm[i//p[j]]=1
    if not f:
      break
  if f:
    print("pairwise coprime")
  else:
    print("setwise coprime")
else:
  print("not coprime")
      


### FIXED CODE ###

def prime(n):
    primes = [0, 1] * (n // 2 + 1)
    if n % 2 == 0:
        primes.pop()
    primes[1] = 0
    primes[2] = 1
    for p in range(3, n + 1, 2):
        if primes[p]:
            for q in range(p * p, n + 1, 2 * p):
                primes[q] = 0
    return primes
pp=prime(10**3)
p=[]
for i in range(2,1001):
  if pp[i]:
    p.append(i)
n=int(input())
a=list(map(int,input().split()))
def gcd(x,y):
  while y:
    x,y=y,x%y
  return x

g=a[0]
for i in a[1:]:
  g=gcd(g,i)
if g==1:
  mm=[0 for i in range(10**6+1)]
  f=True
  for i in a:
    if mm[i] and i!=1:
      f=False
      break
    mm[i]=1
    si=i**0.5
    for j in range(168):
      if p[j]>si:
        break
      if i%p[j]==0 and i!=p[j]:
        if mm[p[j]]:
          f=False
          break
        mm[p[j]]=1
        t=i//p[j]
        if mm[t] and t!=p[j]:
          f=False
          break
        mm[t]=1
    if not f:
      break
  if f:
    print("pairwise coprime")
  else:
    print("setwise coprime")
else:
  print("not coprime")
### BUGGY CODE ###

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

e = [[int(i) for i in input().split()] for j in range(n)]
#print(e)

dp=[[0 for i in range(k+1)] for j in range(n+1)]

for i in range(n-1,-1,-1):
  for j in range(k+1):
    if j < e[i][0]:
      dp[i][j]=dp[i+1][j]
    else:
      dp[i][j]=max(dp[i+1][j],dp[i+1][j-e[i][0]]+e[i][1])

print(max(dp[0]))


### FIXED CODE ###

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

e = [[int(i) for i in input().split()] for j in range(n)]
#print(e)

dp=[[0 for i in range(k+1)] for j in range(n+1)]

for i in range(n-1,-1,-1):
  for j in range(k+1):
    if j < e[i][0]:
      dp[i][j]=dp[i+1][j]
    else:
      dp[i][j]=max(dp[i+1][j],dp[i+1][j-e[i][0]]+e[i][1])

print(max(dp[0]))
### BUGGY CODE ###

N, P = map(int, input().split())
S = input()

ans = 0
if P == 2 or P == 5 :
    for i in range(N) :
        if int(S[i])%P == 0 :
            ans += i+1
    print(ans)
    exit()

modP = [0 for _ in range(P)]
modP[0] = 1
for i in range(N) :
    modP[int(S[i:])%P] += 1

for r in modP :
    ans += r*(r-1)//2

print(ans)


### FIXED CODE ###

N, P = map(int, input().split())
S = input()

ans = 0
if P == 2 or P == 5 :
    for i in range(N) :
        if int(S[i])%P == 0 :
            ans += i+1
    print(ans)
    exit()

modP = [0 for _ in range(P)]
modP[0] = 1
now = 0
t = 1
for i in range(N) :
    now += int(S[-1-i]) * t
    now %= P
    modP[now] += 1
    t = t * 10 % P

for r in modP :
    ans += r*(r-1)//2

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

from collections import deque
n = int(input())
Ps = list(map(int, input().split()))


def toP(h,w):
    return h * n + w

fs = [0] * (n**2)
## フロアフィールドを作る
for i in range(n):
    x = min(i,n-1-i)
    for j in range(n):
        y = min(j,n-1-j)
        fs[i*n+j] = min(x,y)

ans = 0
mvs = [(1,0),(-1,0),(0,1),(0,-1)]
occupied = [1] * (n**2)
for p in Ps:
    p -= 1
    h,w = divmod(p,n)
    ans += fs[p]
    occupied[p] = 0
    q = deque([])
    q.append(p)
    while len(q) > 0: #pを起点にBFS
        p_ = q.popleft()
        h, w = divmod(p_,n)
        dist = fs[p_]
        for dh,dw in mvs:
            if 0<=h+dh<n and 0<=w+dw<n:
                p_next = toP(h+dh,w+dw)
                # ある位置h,wが
                # occupiedなら、隣接マス+1で到達
                # vacantなら、隣接マス+0で到達
                if dist+occupied[p_] < fs[p_next]:
                    q.append(p_next)
                    fs[p_next] = dist + occupied[p_]
print(ans)
    
    

### FIXED CODE ###

from collections import deque
n = int(input())
Ps = list(map(int, input().split()))
Ps = [p-1 for p in Ps]
fs = [0] * (n**2)

## フロアフィールドを作る
for x in range(n**2):
    i,j = divmod(x,n)
    x = min(i,n-1-i)
    y = min(j,n-1-j)
    fs[i*n+j] = min(x,y)

ans = 0
mvs = [1, -1, n, -n]
occupied = [1] * (n**2)
for p in Ps:
    ans += fs[p]
    occupied[p] = 0
    q = deque([])
    q.append(p)
    while len(q) > 0: #pを起点にBFS
        p_ = q.popleft()
        dist = fs[p_]
        for mv in mvs:
            if 0 <= p_+mv < n**2:
                p_next = p_ + mv
                # ある位置h,wが
                # occupiedなら、隣接マス+1で到達
                # vacantなら、隣接マス+0で到達
                if dist+occupied[p_] < fs[p_next]:
                    q.append(p_next)
                    fs[p_next] = dist + occupied[p_]

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

import sys
sys.setrecursionlimit(10**6)

N, Q = list(map(int, input().split()))
# 双方向に張る
tree = [[] for _ in range(N)]
for i in range(N-1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

# queryのスコア表を作る
total = [0 for _ in range(N)]
for i in range(Q):
    p, x = list(map(int, input().split()))
    total[p - 1] += x

# dfs
ans = [0 for _ in range(N)]
def dfs(v, p, value):
    value += total[v]
    ans[v] = value
    for c in tree[v]:
        if c == p: continue
        dfs(c, v, value)

dfs(0, -1, 0)
print(" ".join(list(map(str, ans))))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

readline = sys.stdin.readline
n, q = list(map(int, readline().split()))
# 双方向に張る
tree = [[] for _ in range(n)]
for i in range(n-1):
    a, b = list(map(int, readline().split()))
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

# queryのスコア表を作る
total = [0 for _ in range(n)]
for i in range(q):
    p, x = list(map(int, readline().split()))
    total[p - 1] += x

# dfs
ans = [0 for _ in range(n)]
def dfs(v, p, value):
    value += total[v]
    ans[v] = value
    for c in tree[v]:
        if c == p: continue
        dfs(c, v, value)

dfs(0, -1, 0)
print(*ans)