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

#!/usr/bin/python

import itertools
import sys

def main(argv):
    line = sys.stdin.readline()
    while line:
        N, M, R = map(lambda x: int(x), line.split(" ", 3))
        r  = map(lambda x: int(x) - 1, sys.stdin.readline().split(" "))
        weights = [[0 for i in xrange(N)] for j in xrange(N)]
        for i in xrange(M):
            a, b, c = map(lambda x: int(x), sys.stdin.readline().split(" ", 3))
            weights[a - 1][b - 1] = c
            weights[b - 1][a - 1] = c

        for k in xrange(N):
            for i in xrange(N):
                for j in xrange(N):
                    if weights[i][k] > 0 and weights[k][j] > 0:
                        length = weights[i][k] + weights[k][j]
                        if weights[i][j] == 0 or weights[i][j] > length:
                            weights[i][j] = length

        min_length = -1
        for p in itertools.permutations(r):
            length = 0
            previous = p[0]
            for i in p[1:]:
                length += weights[previous][i]
                previous = i
            if min_length == -1:
                min_length = length
            elif min_length > length:
                min_length = length
        print min_length

        line = sys.stdin.readline()

if __name__ == "__main__":
    main(sys.argv)

### FIXED CODE ###

#!/usr/bin/python

import itertools
import sys

def main(argv):
    line = sys.stdin.readline()
    while line:
        N, M, R = map(lambda x: int(x), line.split(" ", 3))
        r  = map(lambda x: int(x) - 1, sys.stdin.readline().split(" "))
        weights = [[0 for i in xrange(N)] for j in xrange(N)]
        for i in xrange(M):
            a, b, c = map(lambda x: int(x), sys.stdin.readline().split(" ", 3))
            weights[a - 1][b - 1] = c
            weights[b - 1][a - 1] = c

        for k in xrange(N):
            for i in xrange(N):
                for j in xrange(N):
                    if j > i:
                        if weights[i][k] > 0 and weights[k][j] > 0:
                            length = weights[i][k] + weights[k][j]
                            if weights[i][j] == 0 or weights[i][j] > length:
                                weights[i][j] = length
                                weights[j][i] = length

        min_length = -1
        for p in itertools.permutations(r):
            length = 0
            previous = p[0]
            for i in p[1:]:
                length += weights[previous][i]
                previous = i
            if min_length == -1:
                min_length = length
            elif min_length > length:
                min_length = length
        print min_length

        line = sys.stdin.readline()

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

li = list(map(int,input().split()))
nx = [0,0,0]
ans = 0
if all(x&0 for x in li) and li[0] == li[1] == li[2]:
    print(-1)
else:
    while 1:
        if(li[0]%2!=0 or li[1]%2!=0 or li[2]%2!=0):
            break
        nx[0] = (li[1] + li[2])/2
        nx[1] = (li[0] + li[2])/2
        nx[2] = (li[0] + li[1])/2
        li = nx.copy()
        ans += 1
    print(ans)



    



### FIXED CODE ###

li = list(map(int,input().split()))
nx = [0,0,0]
ans = 0
if all(x&1 == 0 for x in li) and li[0] == li[1] == li[2]:
    print(-1)
else:
    while 1:
        if(li[0]%2!=0 or li[1]%2!=0 or li[2]%2!=0):
            break
        nx[0] = (li[1] + li[2])/2
        nx[1] = (li[0] + li[2])/2
        nx[2] = (li[0] + li[1])/2
        li = nx.copy()
        ans += 1
    print(ans)
### BUGGY CODE ###

from collections import deque
INF = 10**9 + 7
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
g = [[] for _ in range(n+1)]
for a, b in ab:
    g[a].append([a, b])
    g[b].append([b, a])
res = [[0, INF] for _ in range(n+1)]
res[1][0] = 1
res[1][1] = 0
q = deque(g[1])
while q:
    q_ = q.pop()
    if res[q_[1]][1] == INF or res[q_[1]][1] > res[q_[0]][1] + 1:
        for gi in g[q_[1]]: q.append(gi)
        res[q_[1]][0] = q_[0]
        res[q_[1]][1] = res[q_[0]][1] + 1
print("Yes")
for i in res[2:]: print(i[0])

### FIXED CODE ###

from collections import deque
INF = 10**9 + 7
n, m = map(int, input().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    g[a].append([a, b])
    g[b].append([b, a])
res = [[0, INF] for _ in range(n+1)]
res[1][1] = 0
q = deque(g[1])
while q:
    q_ = q.popleft()
    if res[q_[1]][1] == INF:
        for gi in g[q_[1]]: q.append(gi)
        res[q_[1]][0] = q_[0]
        res[q_[1]][1] = res[q_[0]][1] + 1
print("Yes")
for i in res[2:]: print(i[0])
### BUGGY CODE ###

s = input()
l = len(s)
t = s.replace('01','').replace('10','')
while s != t:
  s = t
  t = s.replace('01','').replace('10','')
print(l-len(t))

### FIXED CODE ###

s = input()
print(len(s)-abs(s.count('1')-s.count('0')))
### BUGGY CODE ###

rule=input().split()
X=int(rule[0])
K=int(rule[1])
D=int(rule[2])
ans_li=[]
import math
for i in range(K+1):
    ans_pre=X+D*i-D*(K-i)
    ans_li.append(int(math.fabs(ans_pre)))
print(min(ans_li))

### FIXED CODE ###

import math
N=input().split()
X=int(math.fabs(int(N[0])))
K=int(N[1])
D=int(N[2])
if X-K*D>=0:
    print(X-K*D)
else:
    syou=X//D
    x=X-syou*D
    y=X-(syou+1)*D
    if K%2==0:
        if syou%2==0:
            print(x)
        else:
            print(int(math.fabs(y)))
    else:
        if syou%2==0:
            print(int(math.fabs(y)))
        else:
            print(x)
### BUGGY CODE ###

import collections

n = int(input())
count = 0

for i in range(1, n + 1):
	c = collections.Counter(list(str(i)))
	if len(c.keys()) == 3:
		if (c['3'] != 0) and (c['5'] != 0) and (c['7'] != 0):
			count += 1
print(count)

### FIXED CODE ###

n = int(input())
count = 0

def dfs(s):
	if int(s) > n:
		return 0
	if all(s.count(c) > 0 for c in '357'):
		count = 1
	else:
		count = 0
	count += dfs(s + '3')
	count += dfs(s + '5')
	count += dfs(s + '7')
	return count

print(dfs('0'))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from itertools import product
# from itertools import combinations


def solve(N, A):
    bg = []
    sm = []
    # cl = set()
    for i in range(N):
        if A[i] <= i - 1:
            bg.append(i)
            # cl.add(i)
        if A[i] >= 1 - i:
            sm.append(i)
            # cl.add(i)
    # L = list(combinations(cl, 2))
    L = list(product(bg, sm))
    ct = 0
    for l in L:
        if l[0] > l[1]:
            if abs(l[0] - l[1]) == A[l[0]] + A[l[1]]:
                ct += 1
    print(ct)
    # L = list(combinations(range(N), 2))
    # ct = 0
    # for l in L:
    #     if abs(l[0] - l[1]) == A[l[0]] + A[l[1]]:
    #         ct += 1
    # print(ct)
    return

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
            for line in sys.stdin:
                for word in line.split():
                    yield word
    tokens = iterate_tokens()
    N = int(next(tokens))
    A = [int(next(tokens)) for _ in range(N)]
    solve(N, A)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys
from itertools import product
from collections import Counter
# from itertools import combinations


def solve(N, A):
    B = [i - A[i] for i in range(N)]
    C = [i + A[i] for i in range(N)]
    Bc = Counter(B)
    Cc = Counter(C)
    ct = 0
    for k, i in Bc.items():
        if k in Cc:
            ct += i * Cc[k]
    print(ct)
    # bg = []
    # sm = []
    # # cl = set()
    # for i in range(N):
    #     if A[i] <= i - 1:
    #         bg.append(i)
    #         # cl.add(i)
    #     if A[i] >= 1 - i:
    #         sm.append(i)
    #         # cl.add(i)
    # # L = list(combinations(cl, 2))
    # L = list(product(bg, sm))
    # ct = 0
    # for l in L:
    #     if l[0] > l[1]:
    #         if abs(l[0] - l[1]) == A[l[0]] + A[l[1]]:
    #             ct += 1
    # print(ct)
    # # L = list(combinations(range(N), 2))
    # # ct = 0
    # # for l in L:
    # #     if abs(l[0] - l[1]) == A[l[0]] + A[l[1]]:
    # #         ct += 1
    # # print(ct)
    # return

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
            for line in sys.stdin:
                for word in line.split():
                    yield word
    tokens = iterate_tokens()
    N = int(next(tokens))
    A = [int(next(tokens)) for _ in range(N)]
    solve(N, A)

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

N = int(input())
A = list(map(int, input().split()))
m = 10 ** 9 + 7

def Calc(a: int, b: int) -> int:
    return (a * b) % m

ans = 0

for i in range(N):
    for j in range(i + 1, N):
        ans += Calc(A[i], A[j])
        ans = ans % m

print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
m = 10 ** 9 + 7

total = [0] * (N + 1)
for i in range(N):
    total[i + 1] = total[i] + A[i]

total_rev = [0] * (N + 1)
for i in range(N):
    total_rev[i] = total[N] - total[i]

ans = 0
for i in range(N - 1):
    ans = (ans + A[i] * total_rev[i + 1]) % m

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

def LI():return list(map(int,input().split()))
def yes():print("Yes")
def no():print("No")
from collections import deque

def main():
        
    n,m=LI()
    edge=[[]*n for i in range(n)]
    for i in range(m):
        a,b=LI()
        a-=1;b-=1
        edge[a].append(b)
        edge[b].append(a)
    # print(edge)
    
    ans=[-1]*n
    goal=deque([0])
    while (-1 in ans):
        g=goal.popleft()
    
        for i in edge[g]:
            if ans[i]==-1:
                ans[i]=g+1
                goal.append(i)
                
    
    
    # goal=deque([0])
    # while (-1 in ans):
    #     g=goal.popleft()
    #     for i,v in enumerate(edge):
    #         if v==-1:continue
    #         if g in v:
    #             ans[i]=g+1
    #             edge[i]=-1
    #             goal.append(i)
    
    if (-1 in ans):
        no()
        exit()
        
    yes()
    for i in ans[1:]:
        print(i)
main()
    


### FIXED CODE ###

def LI():return list(map(int,input().split()))
def yes():print("Yes")
def no():print("No")
from collections import deque

def main():
    n,m=LI()
    edge=[[] for i in range(n)]
    for i in range(m):
        a,b=LI()
        a-=1;b-=1
        edge[a].append(b)
        edge[b].append(a)    
    ans=[-1]*(n)
    goal=deque([0])
    while goal:
        g=goal.popleft()
        for i in edge[g]:
            if ans[i]==-1:
                ans[i]=g+1
                goal.append(i)
    yes()
    print(*ans[1:])
main()
### BUGGY CODE ###

x,k,d = map(int, input().split())
for i in range(k):
  if x>=0:
    x -= d
    if x<=0:
      if (k-i-1)%2==1:
        x += d
      break
  else:
    x += d
    if x>=0:
      if (k-i-1)%2==1:
        x -= d
      break
print(abs(x))

### FIXED CODE ###

x,k,d = map(int, input().split())
m = abs(x)//d
if m>=k:
  print(abs(x)-k*d)
else:
  k -= m
  if x>=0:
    x -= m*d
  else:
    x += m*d
  
  if x>=0:
    x -= d
    if x<=0:
      if (k-1)%2==1:
        x += d
  else:
    x += d
    if x>=0:
      if (k-1)%2==1:
        x -= d
  print(abs(x))
### BUGGY CODE ###

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

s=input()+'0'
X=[0]*len(s)
for i in range(len(s)):
    if s[i]=='A' and s[i+1]=='C':
        X[i]+=1

A=[]

for i in range(q):
    l,r=map(int,input().split())
    ans=sum(X[l-1:r])
    if s[r-1]=='A' and s[r]=='C':
        A.append(ans-1)
    else:
        A.append(ans)
        
for x in A:
    print(x)

### FIXED CODE ###

n,q=map(int,input().split())
s=input()+'Z'
A=[0]*(n+1)
cnt=0
for i in range(n):
    A[i]=cnt
    if s[i]=='A' and s[i+1]=='C':
        cnt+=1
ANS=[]
for i in range(q):
    l,r=map(int,input().split())
    ANS.append(A[r-1]-A[l-1])
for ans in ANS:
    print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)
N,K=map(int, sys.stdin.readline().split())

al=[ [] for _ in range(N+1) ]	#隣接リスト
for _ in range(N-1):
    a,b=map(int, sys.stdin.readline().split())
    al[a].append(b)
    al[b].append(a)
   
mod=10**9+7
ans=1
def dfs(par,cur,num):
    global ans
    ans*=num
    ans%=mod
    if par==-1: #ルートノードの時は
        num=K-1  #K-1色使用できる
    else:       #ルートノードじゃない時は
        num=K-2  #K-2色使用できる
    for to in al[cur]:
        if to!=par: #遷移候補が親でなければ、遷移
            dfs(cur,to,num)
            num-=1
dfs(-1,1,K)

print ans

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque
import copy

N,K=map(int, sys.stdin.readline().split())

 #階乗　前計算
mod=10**9+7
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, K+1):
    fact_tmp *= i
    fact_tmp %= mod
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, mod-2, mod))

def npr(n,r):
	if n < 0 or r < 0 or n < r:	return 0
	else:	return (fact[n] * inv_fact[n-r]) %mod



nl=[ [] for i in range(N+1) ]	#隣接リスト
C=[ 0 for i in range(N+1) ]	#入次数: 頂点に入ってくる辺数
 
for i in range(N-1):
	a,b=map(int, sys.stdin.readline().split())
	nl[a].append(b)
	C[a]+=1
	nl[b].append(a)
	C[b]+=1


start=1
Visit=[ None for i in range(N+1) ] 
Visit[start]=1
 
p=None		#Parent
q=deque()
q.append( (p,start) )

ans=K

while q:
	p,current=q.popleft()
	flag=0
	for to in nl[current]:
		if Visit[to] is None:
			Visit[to]=1
			q.append( (current,to) )
			flag=1
	if p is None and flag:
		ans*=npr(K-1,C[current])
	elif p is not None and flag:
		ans*=npr(K-2,C[current]-1)
	ans%=mod
		

print ans
### BUGGY CODE ###

import fractions
from functools import reduce
import random
import copy

def gcd(numbers):
    return reduce(fractions.gcd, numbers)

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

for i in range(n):
  b = copy.copy(a)
  b.pop(i)
  t = gcd(b)
  if ans < t:
    ans = t

print(ans)


### FIXED CODE ###

import fractions
from functools import reduce
import random
import copy

def gcd(numbers):
    return reduce(fractions.gcd, numbers)

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

if n < 1000:
  for i in range(n):
    b = copy.copy(a)
    b.pop(i)
    t = gcd(b)
    if ans < t:
      ans = t
else:
  for _ in range(200):
    t = gcd(random.sample(a, 500))
    if ans < t:
      ans = t

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

def main():
    import numpy as np
    inf = 100100100
    ans = inf
    H, W, K = map(int, input().split())
    S = []
    for _ in range(H):
        S.append([int(x) for x in input()])
    S = np.array(S)
    for i in range(2**(H-1)):
        group = [0]
        g = 0
        for j in range(H-1):
            if (i >> j) & 1:
                g += 1
            group.append(g)
        group = np.array(group)
        g += 1
        c = np.array([[0]*W]*g)
        for j in range(H):
            for k in range(W):
                c[group[j],k] += S[j,k]
        num = g-1
        now = np.zeros(g)
        def large(now):
            for n in now:
                if n > K:
                    return True
            else:
                return False
        for k in range(W):
            now += c[:,k]
            if large(now):
                now = c[:,k]
                num += 1
                if large(now):
                    num = inf
                    break
        ans = min(ans, num)
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    import sys
    inf = 100100100
    ans = inf
    H, W, K = map(int, input().split())
    S = [0]*H
    for i in range(H):
        S[i] = [int(x) for x in sys.stdin.readline().strip()]
    for i in range(2**(H-1)):
        group = [0]
        g = 0
        for j in range(H-1):
            if (i >> j) & 1:
                g += 1
            group.append(g)
        g += 1
        c = [[0 for _ in range(W)] for __ in range(g)]
        for j in range(H):
            for k in range(W):
                c[group[j]][k] += S[j][k]
        num = g-1
        now = [0]*g
        def large(now):
            for n in now:
                if n > K:
                    return True
            else:
                return False
        def v_vec(twodlis, k):
            ans = []
            for lis in twodlis:
                ans.append(lis[k])
            return ans
        for k in range(W):
            for n in range(len(now)):
                now[n] = now[n] + v_vec(c,k)[n]
            if large(now):
                now = v_vec(c,k)
                num += 1
                if large(now):
                    num = inf
                    break

        ans = min(ans, num)
    print(ans)

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

# coding: utf-8

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

count = 0

for i in range(0, n):
    xor_result = a[i]
    sum_result = a[i]
    count += 1
    for j in range(i+1, n):
        x = a[j]
        if sum_result & x != 0:
            break
        xor_result ^= x
        sum_result += x
        if xor_result == sum_result:
            count += 1

print(count)


### FIXED CODE ###

# coding: utf-8

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

count = 0
xor_result = 0
sum_result = 0
r = 0

for l in range(0, n):
    while r < n:
        x = a[r]
        if sum_result & x != 0:
            break
        xor_result ^= x
        sum_result += x
        r += 1
    count += r - l
    xor_result ^= a[l]
    sum_result -= a[l]

print(count)
### BUGGY CODE ###

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

def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)

#高速素因数分解

#エラストテネスのふるい
#sieveが0なら素数、0以外ならその値を割り切る素数
def create_sieve(n):
  sieve=[0]*(n+1)
  for i in range(2,n+1):
    if sieve[i]==0:
      for j in range(i*i,n+1,i):
        sieve[j]=i
  return sieve
#素因数分解
#dicではkey=素数、value=何乗か
def prime(n):
  sieve=create_sieve(n)
  dic={}
  while(1):
    if sieve[n]==0:
      dic[n]=dic.get(n,0)+1
      break
    else:
      p=sieve[n]
      dic[p]=dic.get(p,0)+1
      n=n//p
  return dic

def setwise(a):
  l=a[0]
  for i in range(len(a)):
    l=gcd(l,a[i])
  return l==1


if setwise(a):
  check=set()
  for num in a:
    if num!=1:
      dic=prime(num)
      for j in dic:
        if j in check:
          print("setwise coprime")
          exit()
        else:
          check.add(j)
  print("pairwise coprime")
  
else:
  print("not coprime")
  
  
  

### FIXED CODE ###

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

import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans

#エラストテネスのふるい
def create_sieve(n):
  sieve=[0]*(n+1)
  for i in range(2,n+1):
    if sieve[i]==0:
      for j in range(i*i,n+1,i):
        sieve[j]=i
  return sieve

#高速素因数分解
def fast_factorization(n, sieve):
  prime={}
  while n>1:
    p=sieve[n]
    #nが素数の場合
    if p==0:
      prime[n]=prime.get(n,0)+1
      break
    #nが素数ではない場合
    else:
      prime[p]=prime.get(p,0)+1
      n=n//p
  return prime

check=set()
if setwise_coprime(a)==1:
  #素因数のダブリをcheck
  sieve=create_sieve(10**6)
  for i in range(n):
    if a[i]!=1:
      s=fast_factorization(a[i], sieve)
      for i in s:
        if i in check:
          print("setwise coprime")
          sys.exit()
        else:
          check.add(i)
  print("pairwise coprime")    
else:
  print("not coprime")
### BUGGY CODE ###

n, m = map(int, input().split())
ANS = [-1]*(n+1)
P = []
L = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())

    if a == 1:
        ANS[b] = 1
        P.append(b)
    elif b == 1:
        ANS[a] = 1
        P.append(a)
    else:    
        L[a].append(b)
        L[b].append(a)

# print(L, ANS, P)

i = 0
while len(P) < n-1:
    for j in range(1, n+1):
        if P[i] in L[j] and ANS[j] == -1:
            P.append(j)
            L[j].remove(P[i])
            ANS[j] = P[i]
            # print(i, P[i], j, L, ANS, P)
    i += 1

print('Yes')
for i in range(2, n+1):
    print(ANS[i])


### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
L = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)

# 幅優先探索
d = deque([0])
D = [-1] * n
D[0] = 0
while len(d) > 0 :
    t = d.popleft()
    for i in L[t]:
        if D[i] == -1:
            D[i] = t
            d.append(i)
            # print(d, D)

print('Yes')
for i in range(1, n):
    print(D[i]+1)
### BUGGY CODE ###

import sys
from collections import deque
H,W=map(int,input().split())
A=[[c for c in l.strip()] for l in sys.stdin]
maze=[[3000]*W for i in range(H)]
q=deque([])
start=[]
dy=[1,0,-1,0]
dx=[0,1,0,-1]
for i in range(H):
  for j in range(W):
    if(A[i][j]=="#"):
      start.append((i,j))
#print(start)
x=0
y=maze[:]
for i in start:
  maze=[[3000]*W for i in range(H)]
  q.append(i)
  maze[i[0]][i[1]]=0
  while(q):
    c=q.popleft()
    y[c[0]][c[1]]=min(y[c[0]][c[1]],maze[c[0]][c[1]])
    for j in range(4):
      if(c[0]+dy[j]>=0 and c[0]+dy[j]<H and c[1]+dx[j]>=0 and c[1]+dx[j]<W):
        if(maze[c[0]+dy[j]][c[1]+dx[j]]==3000 and A[c[0]+dy[j]][c[1]+dx[j]]=="."):
          q.append((c[0]+dy[j],c[1]+dx[j]))
          maze[c[0]+dy[j]][c[1]+dx[j]]=maze[c[0]][c[1]]+1
          
          #y=max(y,maze[c[0]+dy[j]][c[1]+dx[j]])

for i in range(H):
  x=max(x,max(y[i]))
print(x)

### FIXED CODE ###

import sys
from collections import deque
H,W=map(int,input().split())
A=[[c for c in l.strip()] for l in sys.stdin]
maze=[[3000]*W for i in range(H)]
q=deque([])
start=[]
dy=[1,0,-1,0]
dx=[0,1,0,-1]
for i in range(H):
  for j in range(W):
    if(A[i][j]=="#"):
      q.append((i,j))
#print(start)
x=0
y=maze[:]

for i in q:
  maze[i[0]][i[1]]=0
while(q):
  c=q.popleft()
  for j in range(4):
    if(c[0]+dy[j]>=0 and c[0]+dy[j]<H and c[1]+dx[j]>=0 and c[1]+dx[j]<W):
      if(maze[c[0]+dy[j]][c[1]+dx[j]]==3000 and A[c[0]+dy[j]][c[1]+dx[j]]=="."):
        q.append((c[0]+dy[j],c[1]+dx[j]))
        maze[c[0]+dy[j]][c[1]+dx[j]]=maze[c[0]][c[1]]+1
        
        x=max(x,maze[c[0]+dy[j]][c[1]+dx[j]])
print(x)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = 10**9+7
s = 0
for i in range(n-1):
  s += a[i] * sum(a[i+1:])
print(s % b)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
s = 0
c = sum(a)
for i in range(n-1):
  c -= a[i]
  s += a[i] * c
print(s % (10**9+7))
### BUGGY CODE ###

H,W,K=map(int,input().split())
A=[input() for i in range(H)]
for i,l in enumerate(A):
    if 'S' in l:
        S=((1,0,K),i,l.index('S'))
q=[S]
from heapq import heappop,heappush
n=((0,1),(0,-1),(1,0),(-1,0))
v=[[0]*W for i in range(H)]
v[S[1]][S[2]]=1
a=999
#M=[[999]*H for i in range(W)]
while q:
    (s,m,o),i,j=heappop(q)
    #M[i][j]=min(s,M[i][j])
    if i in (0,H-1) or j in (0,W-1):
        a=min(a,s)
    for x,y in n:
        if 0<=i+x<H and 0<=j+y<W:
            if v[i+x][j+y]:continue
            v[i+x][j+y]=1
            if A[i+x][j+y]=='.':
                if m<K:
                    heappush(q,((s,m+1,o),i+x,j+y))
                else:
                    heappush(q,((s+1,1,o-K),i+x,j+y))
            elif A[i+x][j+y]=='#':
                if m<K and o<K:
                    heappush(q,((s,m+1,o+1),i+x,j+y))
                else:
                    heappush(q,((s+1,1,o-K+1),i+x,j+y))
print(a)
#print(*M,sep='\n')

### FIXED CODE ###

H,W,K=map(int,input().split())
A=[input() for i in range(H)]
for i,l in enumerate(A):
    if 'S' in l:
        S=(K,i,l.index('S'))
from collections import deque
q=deque([S])
X=[(S[1],S[2])]
n=((0,1),(0,-1),(1,0),(-1,0))
v=[[0]*W for i in range(H)]
v[S[1]][S[2]]=1
while q:
    m,i,j=q.popleft()
    for x,y in n:
        if 0<=i+x<H and 0<=j+y<W:
            if v[i+x][j+y]:continue
            v[i+x][j+y]=1
            if A[i+x][j+y]=='.' and m>0:
                q.append((m-1,i+x,j+y))
                X.append((i+x,j+y))
print(min([min(0--i//K,0--(H-i-1)//K,0--j//K,0--(W-j-1)//K) for i,j in X])+1)