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

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

ans = 0
seat = [[min(i, j, n-i-1, n-j-1) for j in range(n)] for i in range(n)]
reserved = [[True for j in range(n)] for i in range(n)]

vec = [(-1, 0), (1, 0), (0, -1), (0, 1)]

for i in range(n**2):
    v = p[i]-1
    x, y = v//n, v % n
    reserved[x][y] = False
    ans += seat[x][y]
    q = [(x, y)]
    while q:
        x, y = q.pop()
        for dx, dy in vec:
            x1 = x+dx
            y1 = y+dy
            if 0 <= x1 < n and 0 <= y1 < n and seat[x1][y1] > seat[x][y] + reserved[x][y]:
                seat[x1][y1] = seat[x][y] + reserved[x][y]
                q.append((x1, y1))

print(ans)


### FIXED CODE ###

n = int(input())
p = [int(x) for x in input().split()]

ans = 0
seat = [[min(i, j, n-i-1, n-j-1) for j in range(n)] for i in range(n)]
reserved = [[True for j in range(n)] for i in range(n)]

vec = [(-1, 0), (1, 0), (0, -1), (0, 1)]

for i in range(n**2):
    v = p[i]-1
    x, y = v//n, v % n
    reserved[x][y] = False
    ans += seat[x][y]
    q = [(x, y)]
    while q:
        x, y = q.pop()
        if 0 <= x+1 < n and 0 <= y < n and seat[x+1][y] > seat[x][y] + reserved[x][y]:
            seat[x+1][y] = seat[x][y] + reserved[x][y]
            q.append((x+1, y))
        if 0 <= x-1 < n and 0 <= y < n and seat[x-1][y] > seat[x][y] + reserved[x][y]:
            seat[x-1][y] = seat[x][y] + reserved[x][y]
            q.append((x-1, y))
        if 0 <= x < n and 0 <= y+1 < n and seat[x][y+1] > seat[x][y] + reserved[x][y]:
            seat[x][y+1] = seat[x][y] + reserved[x][y]
            q.append((x, y+1))
        if 0 <= x < n and 0 <= y-1 < n and seat[x][y-1] > seat[x][y] + reserved[x][y]:
            seat[x][y-1] = seat[x][y] + reserved[x][y]
            q.append((x, y-1))


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

def main():
    N = int(input())
    A = []
    for i in range(N):
        A.append(int(input()))
    for j in range(N):
        a = A[j]
        A[j] = -1
        print(max(A))
        A[j] = a


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    maximum = 0
    next_maximum = 0
    A = []
    for _ in range(N):
        a = int(input())
        A.append(a)
        if a > maximum:
            maximum = a
        elif a > next_maximum:
            next_maximum = a
    for b in A:
        if b == maximum:
            print(next_maximum)
        else:
            print(maximum)


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

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    S=input()
    T=input()
    dp=[['']*(len(T)+1) for _ in range(len(S)+1)]
    for s in range(len(S)):
        for t in range(len(T)):
            if S[s]==T[t]:
                dp[s+1][t+1]=dp[s][t]+S[s]
            else:
                if len(dp[s+1][t])>len(dp[s][t+1]):
                    dp[s+1][t+1]=dp[s+1][t]
                else:
                    dp[s+1][t+1]=dp[s][t+1]
    print(dp[len(S)][len(T)])

if __name__ == '__main__':
    main()


### FIXED CODE ###

S=list(input())
T=list(input())

dp = [[0]*(len(T)+1) for i in (range(len(S)+1))]

for s in range(len(S)):
    for t in range(len(T)):
        if S[s] == T[t]:
            dp[s+1][t+1] = max(dp[s][t]+1,dp[s][t+1],dp[s+1][t])
        else:
            dp[s+1][t+1] = max(dp[s][t+1],dp[s+1][t])

def checkdpn(x,y):
    if dp[x][y] == dp[x-1][y] + 1 and dp[x][y] == dp[x][y-1] + 1:
        return True
    else:
        return False

x = len(S)
y = len(T)
str = ''

while(True):
    if checkdpn(x,y):
        str = S[x-1] + str
        x -= 1
    else:
        if dp[x][y] == dp[x][y-1] + 1:
            x -= 1
        else:
            y -= 1
    if dp[x][y] == 0:
        break
print(str)
### BUGGY CODE ###

N, K = map( int, input().split())
ans = 0
for a in range(K,N+1):
    for b in range(1,a):
        if a%b >= K:
            ans += 1
    ans += N - a
print(ans)

### FIXED CODE ###

N,K = map( int, input().split())
ans = 0
if K == 0:
    ans = N**2
else:
    for b in range(K+1,N+1):
        ans += ((N+1)//b)*(b-K) + max(0, N - ((N+1)//b)*b-(K -1))
print(int(ans))
### BUGGY CODE ###

N, Q = map(int, input().split())
#graph = [[] for i in range(200010)]
#ans = [0 for i in range(200010)]
graph = [set() for i in range(N)]
ans = [0 for i in range(N)]
import sys
#sys.setrecursionlimit(100000)
sys.setrecursionlimit(10**7)


for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1

    #graph[a].append(b)
    #graph[b].append(a)
    graph[a].add(b)
    graph[b].add(a)

for _ in range(Q):
    p, x = map(int, input().split())
    p -= 1

    ans[p] += x

def dfs(node, frm=-1):
    for to in graph[node]:
        if to == frm:
            continue
        ans[to] += ans[node]
        dfs(to, node)
dfs(0)

print(*ans)

### FIXED CODE ###

N, Q = map(int, input().split())
graph = [[] for i in range(200010)]
ans = [0 for i in range(200010)]
import sys
#sys.setrecursionlimit(100000)
sys.setrecursionlimit(10**7)
#
readline = sys.stdin.readline


for _ in range(N - 1):
    #a, b = map(int, input().split())
    a, b = map(int, readline().split())
    a -= 1
    b -= 1

    graph[a].append(b)
    graph[b].append(a)

for _ in range(Q):
    #p, x = map(int, input().split())
    p, x = map(int, readline().split())
    p -= 1

    ans[p] += x

def dfs(node, frm=-1):
    for to in graph[node]:
        if to == frm:
            continue
        ans[to] += ans[node]
        dfs(to, node)
dfs(0)

print(*ans[:N])
### BUGGY CODE ###

x, y, z, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
r = [0] * x * y
tmp = min(k, x * y)
r2 = [0] * tmp * z
n = 0
for i in range(x):
  for j in range(y):
      r[n] = a[i] + b[j]
      n += 1
r.sort(reverse=True)
r = r[:tmp]
n = 0
for i in range(tmp):
  for j in range(z):
      r2[n] = r[i] + c[j]
      n += 1
r2.sort()
for i in range(k):
  print(r2[-(i+1)])


### FIXED CODE ###

import numpy as np

x, y, z, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
r = []
for i in range(x):
  for j in range(y):
    if (i + 1) * (j + 1) > k:
        break
    for l in range(z):
      if (i + 1) * (j + 1) * (l + 1) > k:
        break
      r.append(a[i] + b[j] + c[l])
r.sort()
for i in range(k):
  print(r[-(i+1)])
### BUGGY CODE ###

from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    X = int(input())
    import math
    b = -2000000
    #for b in range(-200000,200000,1):
    while True:
        a = X + pow(b,5)
        if a != 0:
            p = pow(a,-5)
        #print(a,b,p)
        if int(p) == p:
            print(a,b)
            exit()
        b += 1
if __name__ == '__main__':
  main()


### FIXED CODE ###

from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    X = int(input())
    import math
    for i in range(-119,119):
        for j in range(-119,119):
            if i == j:
                continue
            if X % (i - j) == 0:
                if (i-j) * (pow(i,4) + pow(i,3)*j + pow(i,2)*pow(j,2) + i*pow(j,3) + pow(j,4)) == X:
                    print(i,j)
                    exit()
if __name__ == '__main__':
  main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

graph = [[] for _ in range(n)]
for i in range(n-1):
    graph[uvw[i][0]-1].append((uvw[i][1]-1, uvw[i][2]))
    graph[uvw[i][1]-1].append((uvw[i][0]-1, uvw[i][2]))

stack = [0]
visited = []
ans = [0]*n
while stack:
    node = stack.pop()
    visited.append(node)
    for child in graph[node]:
        if child[0] in visited:
            continue
        
        stack.append(child[0])
        if child[1]%2 == 0:
            ans[child[0]] = ans[node]
        else:
            ans[child[0]] = (ans[node]+1)%2

[print(ans[i]) for i in range(n)]

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

graph = [[] for _ in range(n)]
for i in range(n-1):
    graph[uvw[i][0]-1].append((uvw[i][1]-1, uvw[i][2]))
    graph[uvw[i][1]-1].append((uvw[i][0]-1, uvw[i][2]))

stack = [0]
ans = [-1]*n
ans[0] = 0
while stack:
    node = stack.pop()
    for child in graph[node]:
        if ans[child[0]]!=-1:
            continue
        
        stack.append(child[0])
        if child[1]%2 == 0:
            ans[child[0]] = ans[node]
        else:
            ans[child[0]] = (ans[node]+1)%2

for a in ans:
    print(a)
### BUGGY CODE ###

#-*- coding:utf-8 -*-

n, k, q = map(int, input().split())
a_li = [int(input()) for i in range(q)]

pt_li = [] #所持点数のリストを作る
for i in range(n):
    pt_li.append(k)

for t in range(q):
    for u in range(n):
        pt_li[u] -= 1
    pt_li[a_li[t]-1] += 1

for s in range(n):
     if pt_li[s] <= 0:
         print("No")
     else:
         print("Yes")


### FIXED CODE ###

#-*- coding:utf-8 -*-

n, k, q = map(int, input().split())
a_li = [int(input()) for i in range(q)]

b_li = [0]*n

for i in range(q):
    b_li[a_li[i]-1] += 1

for t in range(n):
    pt = k -q + b_li[t]
    if pt > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n = int(input())
botan = [int(input()) for i in range(n)]
light = 1 # 1番目のボタンが初め光ってる
count = 1
exi = [1]
while True:
    light = botan[light - 1]
    if light in exi:
        print(-1)
        exit()
        break
    exi.append(light)
    
    if 2 in exi:
        print(count)
        exit()
        break
    count += 1

### FIXED CODE ###

n = int(input())
botan = [int(input()) for i in range(n)]
light = 0 # 1番目のボタンが初め光ってる
count = 0

for i in range(n):
    light = botan[light] - 1
    if light == 1:
        break
    
if i == n - 1:
    print(-1)
else:
    print(i + 1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

N,Q = map(int,input().split())
AB = [[x for x in map(int,input().split())] for _ in range(N-1)]
PX = [[x for x in map(int,input().split())] for _ in range(Q)]

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

cnt = [0]*N
for p,x in PX:
    cnt[p-1] += x

def dfs(v,parent,add):
    for w in graph[v]:
        if w != parent:
             cnt[w-1] += add
             dfs(w,v,cnt[w-1])

for i in graph[1]:
    cnt[i-1] += cnt[0]
    dfs(i,1,cnt[i-1])

print(*cnt)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

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

value = [0] * (N+1)
for p,x in PX:
    value[p] += x

def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])

dfs(1,0,0)

answer = ' '.join(map(str,value[1:]))
print(answer)
### BUGGY CODE ###

from itertools import accumulate
n = int(input())
s = str(input())
tt = [1 if i  == "W" else 0 for i in s]
B = [0] + tt
B = list(accumulate(B))
#print(B)
ans = float('Inf')
for i in range(0,n):
    #w = s[:i].count("W")
    ##W = sum(tt[:i])
    w = B[i]
    #print(W,w)
    #e = s[i:].count("E")
    E = len(tt[i:]) - sum(tt[i:])
    e = n - i - B[-1] + B[i]
    #print(E,e)
    #ans = min(ans,W+E)
    ans = min(ans,w+e)
print(ans)

### FIXED CODE ###

from itertools import accumulate
n = int(input())
s = str(input())
tt = [1 if i  == "W" else 0 for i in s]
B = [0] + tt
B = list(accumulate(B))
#print(B)
ans = float('Inf')
for i in range(0,n+1):
    #w = s[:i].count("W")
    ##W = sum(tt[:i])
    w = B[i]
    #print(W,w)
    #e = s[i:].count("E")
    #E = len(tt[i:]) - sum(tt[i:])
    e = n - i - B[-1] + B[i]
    #print(E,e)
    #ans = min(ans,W+E)
    ans = min(ans,w+e)
print(ans)
### BUGGY CODE ###

N,Y= map(int,input().split())
ans = 0
for i in reversed(range(Y//10000+1)):
    for j in reversed(range(Y//5000+1)):
        k = N -i-j
        if i * 10000 + j * 5000 + k *1000 == Y and k>-1:
            print(str(i)+" "+str(j)+" "+str(k))
            exit()
print("-1 -1 -1")

### FIXED CODE ###

#085 C

N,Y = map(int, input().split())
A =10000
B =5000
C =1000

for i in range((N)+1):
    for j in range(N+1-i):
        k = N-(i+j)
        if i * A + j * B + k * C == Y and k >= 0:
            print(str(i)+" "+str(j)+" "+str(k))
            exit()
                
print("-1 -1 -1")
### BUGGY CODE ###

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

a=list(map(int,input().split()))
f=list(map(int,input().split()))
cnt=[]
a.sort()
f.sort(reverse=True)
for i in range(n):
    cv=a[i]*f[i]
    cnt.append(cv)

def judge(s):
    tmp=k
    for i in range(n):
        if cnt[i]>s:
            if (cnt[i]-s)%f[i]==0:
                vv=(cnt[i]-s)//f[i]
            else:
                vv=1+(cnt[i]-s)//f[i]
            tmp-=vv
    if tmp<0:
        return False
    return True

left=-1
right=10**18

while left+1<right:
    mid=(left+right)//2
    if judge(mid):
        right=mid
    else:
        left=mid

print(right)

### FIXED CODE ###

# tempt
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N,K = map(int,readline().split())
A = np.array(readline().split(),np.int64)
F = np.array(readline().split(),np.int64)

A.sort(); F.sort(); F=F[::-1]

Asum = A.sum()

def test(x):
    # 全員がx秒以下に収めるための必要コストがK以下である
    return Asum - np.minimum(A,x//F).sum() <= K

left = -1 # 不可能目標
right = 10**13 # 可能目標
while left+1 < right:
    mid = (left+right)//2
    if test(mid):
        right = mid
    else:
        left = mid

answer = right
print(answer)
### BUGGY CODE ###

X, K, D = map(int, input().split())


if X > 0:
    cur_abs = abs(X)
    while K > 0:
        X -= D
        if abs(X) > cur_abs:
            X += D
            break
        cur_abs = abs(X)
        K -= 1
    K = K % 2
    if K % 2 != 0:
        print(min(abs(X + D), abs(X - D)))
    else:
        print(cur_abs)
elif X < 0:
    cur_abs = abs(X)
    while K > 0:
        X += D
        if abs(X) > cur_abs:
            X -= D
            break
        cur_abs = abs(X)
        K -= 1
    K = K % 2
    if K % 2 != 0:
        print(min(abs(X + D), abs(X - D)))
    else:
        print(cur_abs)
else:   # X == 0
    if K % 2 == 0:
        print(0)
    else:
        print(min(abs(X + D), abs(X - D)))


### FIXED CODE ###

X, K, D = map(int, input().split())

if X > 0:
    k = X // D
    if k <= K:
        X -= D * k
        K -= k
    else:
        X -= D * K
        K = 0
        print(abs(X))
        exit()

    cur_abs = abs(X)
    while K > 0:
        X -= D
        if abs(X) > cur_abs:
            X += D
            break
        cur_abs = abs(X)
        K -= 1
    K = K % 2
    if K % 2 != 0:
        print(min(abs(X + D), abs(X - D)))
    else:
        print(cur_abs)


elif X < 0:
    k = abs(X) // D
    if k <= K:
        X += D * k
        K -= k
    else:
        X += D * K
        K = 0
        print(abs(X))
        exit()

    cur_abs = abs(X)
    while K > 0:
        X += D
        if abs(X) > cur_abs:
            X -= D
            break
        cur_abs = abs(X)
        K -= 1
    K = K % 2
    if K % 2 != 0:
        print(min(abs(X + D), abs(X - D)))
    else:
        print(cur_abs)


else:   # X == 0
    if K % 2 == 0:
        print(0)
    else:
        print(min(abs(X + D), abs(X - D)))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np
import sys
input = sys.stdin.readline

N, K, Q = map(int, input().split())
score = np.array([K]*N)


for i in range(Q):
    score[int(input()) - 1] += 1
    score = score - 1


for SCORE in score:
    if SCORE <= 0:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline

N, K, Q = map(int, input().split())
score = [0] * N

for i in range(Q):
    score[int(input()) -1 ] += +  1

for SCORE in score:
    if SCORE <= Q - K:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

N = int(input())
X = list(map(int,input().split()))
import copy
for i in range(N):
  ls = copy.copy(X)
  ls.pop(i)
  sorted_ls = sorted(ls)
  print(sorted_ls[((len(sorted_ls)+1)//2-1)])

### FIXED CODE ###

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

sX = sorted(X)
small_median = sX[N//2-1]
large_median = sX[N//2]

for i in range(N):
  if X[i] <= small_median:
    print(large_median)
  else:
    print(small_median)
### BUGGY CODE ###

a=int(input())
a1 = a // 2
b1=list(input().split( ))
b=list(map(int, b1))
d=[]
for j in range(a):
    e=b[:]
    for k in range(a1):
        c=(j+1+2*k)%a
        e[c]=e[c]*(-1)
    d.append(sum(e))

print(' '.join(map(str, d)))


### FIXED CODE ###

a=int(input())
a1 = a // 2
b1=list(input().split( ))
b=list(map(int, b1))
d=[]

s1=0
for j in range(a1):
    s1 += b[(2*j + 1)]
x1 = sum(b) - 2 * s1
d.append(x1)

for k in range(a-1):
    x = 2 * b[k] - d[k]
    d.append(x)

print(' '.join(map(str, d)))
### BUGGY CODE ###

N,M=map(int,input().split())
if N==1:
    print(M)
    exit()

for i in range(N,M+1):
    if M%i==0:
        print(M//i)
        exit()

### FIXED CODE ###

N,M=map(int,input().split())
if N==1:
    print(M)
    exit()

if N>=M**0.5:
    for i in range(M//N,0,-1):
        if M%i==0:
            print(i)
            exit()
else:
    for i in range(N,M+1):
        if M%i==0:
            print(M//i)
            exit()
print(1)
### BUGGY CODE ###

# -*- coding utf-8 -*-

H, W = map(int, input().split())
field = []    # field[h][w]

for i in range(H):
    field.append(list(input()) + ['#'])
field.append(['#'] * (W + 1))

ans = 0

beam_h = [[0] * W for _ in range(H)]
for h in range(H):
    l = 0
    r = 0
    while r < W + 1:
        num = 0
        while field[h][r] == '.':
            r += 1
            num += 1
        if l != r:
            beam_h[h][l:r] = [num] * num
            ans = max(ans, num)
            l = r
        l += 1
        r += 1

beam_w = [[0] * W for _ in range(H)]
for w in range(W):
    l = 0
    r = 0
    while r < H + 1:
        num = 0
        while field[r][w] == '.':
            r += 1
            num += 1
        if l != r:
            # beam_w[l:r][w] = [num] * num
            for i in range(l, r):
                beam_w[i][w] = num
                ans = max(ans, beam_w[i][w] + beam_h[i][w] - 1)
            l = r
        l += 1
        r += 1

print(ans)


### FIXED CODE ###

# -*- coding utf-8 -*-

H, W = map(int, input().split())
field = []    # field[h][w]

for i in range(H):
    field.append(list(input()) + ['#'])
field.append(['#'] * (W + 1))

ans = 0

beam_h = [[0] * W for _ in range(H)]
for h in range(H):
    l = 0
    r = 0
    while r < W + 1:
        num = 0
        while field[h][r] == '.':
            r += 1
            num += 1
        if l != r:
            beam_h[h][l:r] = [num] * num
            ans = max(ans, num)
            l = r
        l += 1
        r += 1

beam_w = [[0] * W for _ in range(H)]
for w in range(W):
    l = 0
    r = 0
    while r < H + 1:
        num = 0
        while field[r][w] == '.':
            r += 1
            num += 1
        if l != r:
            # beam_w[l:r][w] = [num] * num
            for i in range(l, r):
                beam_w[i][w] = num
                ans = max(ans, beam_w[i][w] + beam_h[i][w] - 1)
            l = r
        l += 1
        r += 1

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

from collections import deque
H, W = map(int, input().split())
S = [input() + "#" for _ in range(H)]
S.append("#" * (W + 1))
paths = [(h, w) for h in range(H) for w in range(W) if S[h][w] == "."]

ans = 0
todo = deque()
for sh, sw in paths:
    for gh, gw in paths:
        if sh == gh and sw == gw:
            continue
        todo.append((0, sh, sw))
        pathed = [[False] * W for _ in range(H)]
        while todo:
            cnt, h, w = todo.popleft()
            cnt += 1
            for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nh = h + dh
                nw = w + dw
                if nh == gh and nw == gw:
                    if ans < cnt:
                        ans = cnt
                    todo.clear()
                    break
                elif S[nh][nw] == "." and not pathed[nh][nw]:
                    todo.append((cnt, nh, nw))
            pathed[h][w] = True
print(ans)

### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
S = [input() + "#" for _ in range(H)]
S.append("#" * (W + 1))

todo = deque()
done = set()
ans = 0
for sh in range(H):
    for sw in range(W):
        if S[sh][sw] == "#":
            continue
        s = (sh, sw)
        done.clear()
        done.add(s)
        todo.append((s, 0))
        while todo:
            p, count = todo.popleft()
            ncount = count + 1
            for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nh, nw = p[0] + dh, p[1] + dw
                if S[nh][nw] == "#":
                    continue
                np = (nh, nw)
                if np in done:
                    continue
                done.add(np)
                ans = max(ans, ncount)
                todo.append((np, ncount))
print(ans)
### BUGGY CODE ###

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

order = [0] * n

for ii in range(n):
    order[ii] = a.index(a_new[ii])+1
    print(order[ii])



### FIXED CODE ###

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

a_new = sorted(range(len(a)), key=lambda k: a[k])
for ii in range(n):
    print(a_new[ii]+1)
### BUGGY CODE ###

from itertools import product, combinations
N,M,K=map(int, raw_input().split())

mod=10**9+7
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, N*M+1):
    fact_tmp *= i
    fact_tmp %= mod
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, mod-2, mod))
 
 
def ncr(n,r):
	if n < 0 or r < 0 or n < r:	return 0
	else:	return (fact[n] * inv_fact[r] * inv_fact[n-r]) %mod


torisuu=ncr(N*M-2,K-2)
Zahyou=list( product(range(N), range(M)) )
Combi=list( combinations( range(N*M), 2) )


ans=0
for first, second in Combi:
	unit_cost=abs( Zahyou[second][0]-Zahyou[first][0] ) + abs(Zahyou[second][1]-Zahyou[first][1])
	unit_cost%=mod
	ans+=unit_cost*torisuu
	ans%=mod

print ans

### FIXED CODE ###

from itertools import product, combinations
N,M,K=map(int, raw_input().split())


mod=10**9+7
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, N*M+1):
    fact_tmp *= i
    fact_tmp %= mod
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, mod-2, mod))
 
 
def ncr(n,r):
	if n < 0 or r < 0 or n < r:	return 0
	else:	return (fact[n] * inv_fact[r] * inv_fact[n-r]) %mod


torisuu=ncr(N*M-2,K-2)

ans=0
for i in range(N):
	for j in range(M):
		l_sum=(1+j)*j/2*N		#left
		r_sum=(1+(M-j-1))*(M-j-1)/2*N	#right	
		u_sum=(1+i)*i/2*M		#upper
		d_sum=(1+(N-i-1))*(N-i-1)/2*M	#down
		ans+=(l_sum+r_sum+u_sum+d_sum)*torisuu
		ans%=mod

print ( ans*pow(2,mod-2,mod) ) %mod