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

#!/usr/bin/env python

from copy import deepcopy

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, = read_line(int)
a = read_line(*([int] * n))

def price(aa):
    sum = 0
    for j in range(len(aa) - 1):
        sum += abs(aa[j] - aa[j + 1])

    return sum

for i in range(len(a)):
    aa = deepcopy(a)

    del aa[i]

    aa = [0] + aa + [0]

    print(price(aa))


### FIXED CODE ###

#!/usr/bin/env python

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, = read_line(int)
a = read_line(*([int] * n))

def price(aa):
    sum = 0

    prev = 0
    for i in range(len(aa)):
        sum += abs(prev - aa[i])
        prev = aa[i]

    sum += abs(prev)
    return sum

aa = [0] + a + [0]
price_all = 0

for i in range(len(aa) - 1):
    price_all += abs(aa[i] - aa[i + 1])

for i in range(1, len(aa) - 1):
    p = price_all
    p -= abs(aa[i - 1] - aa[i])
    p -= abs(aa[i] - aa[i + 1])
    p += abs(aa[i - 1] - aa[i + 1])
    print(p)
### BUGGY CODE ###

def GCD(x,y):
    x,y=max(x,y),min(x,y)
    if x%y==0:
        return y
    else:
        return GCD(y,x%y)

def LCM(x,y):
    return x*y//GCD(x,y)

# modulo:mod

# inverse x^(-1)
def inv(x):
    global mod
    return pow(x,mod-2,mod)

mod = 10 ** 9 + 7

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

ans = 0
l = 1
for Ai in A:
    li = LCM(l, Ai)
    ans = (ans * (li // l)) % mod
    ans = (ans + li // Ai) % mod
    l = li

print (ans)

### FIXED CODE ###

# prim factorization
def prfct(n):
    l=[]
    if n%2==0:
        m=0
        while n%2==0:
            n//=2
            m+=1
        l.append((2,m))
    p=3
    while p**2<=n:
        if n%p==0:
            m=0
            while n%p==0:
                n//=p
                m+=1
            l.append((p,m))
        p+=2
    if n>1:
        l.append((n,1))
    return l

# modulo:mod

# inverse x^(-1)
def inv(x):
    global mod
    return pow(x,mod-2,mod)

mod = 10 ** 9 + 7

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

mp = {}

pfs = []
for Ai in A:
    pf = prfct(Ai)
    for pr, pw in pf:
        if pr not in mp:
            mp[pr] = pw
        else:
            mp[pr] = max(mp[pr], pw)
    pfs.append(pf)
# print(pfs)
# print(mp)

l = 1
for pr in mp:
    pw = mp[pr]
    l *= pow(pr, pw, mod)
# print(l)

ans = 0

for pf in pfs:
    temp = 1
    for prw in pf:
        pr, pw = prw
        temp = temp * pow(pr, pw, mod) % mod
    temp2 = l * inv(temp) % mod
    ans = (ans + temp2) % mod

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

N = int(input())
T = [int(input()) for _ in range(N)]

T = list(set(T))
T.sort(reverse=True)

T_max = T[len(T) - 1]
count = 1
flag_1 = True
while flag_1:
    check = T_max * count 
    flag_2 = True
    for i in T:
        if check % i != 0:
            flag_2 = False
            break
    if flag_2 == True:
        print(T_max * count)
        flag_1 = False
    count += 1

### FIXED CODE ###

N = int(input())
T = [int(input()) for _ in range(N)]

def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
      
from functools import reduce
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
  
print(lcm_list(T))
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    P = list(map(int, input().split()))
    r = 0
    for i in range(n-k+1):
        t = sum(P[i:i+k])
        r = r if r>t else t
    print((r+k)/2)

main()

### FIXED CODE ###

def func(x):
    return (x+1)/2

n, k = map(int, input().split())
P = list(map(func, map(int, input().split())))
t = sum(P[0:k])
r = t
for i in range(n-k):
    t = t-P[i]+P[i+k]
    r = r if r>t else t
print(r)
### BUGGY CODE ###

n = int(input())
x = [int(input()) for i in range(n)]
x.sort()
answer = 0
while x != []:
	num,y = 0,x[0]
	while x != [] and x[0] == y:
		num += 1
		x = x[1:]
	if num%2==1:
		answer += 1
print(answer)

### FIXED CODE ###

import collections
n = int(input())
x = [int(input()) for i in range(n)]
a = collections.Counter(x)
answer = 0
for i in a.values():
	if i%2==1:
		answer += 1
print(answer)
### BUGGY CODE ###

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


counter = N  # l != rの場合を以下では考える
for l in range(N):
    r = l - 1
    while r < N-1:
        r += 1
        sum_A = sum(A[l:r+1])
        if r == l:
            xor_A = A[r]
        else:
            xor_A = xor_A ^ A[r]
            if xor_A == sum_A:
                counter += 1



print(counter)

### FIXED CODE ###

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

ans = 0
r = 0
xor_A = 0
for l in range(N):
    while (r < N and (xor_A ^ A[r]) == (xor_A + A[r])):
        xor_A += A[r]
        r += 1
    ans += r - l
    if l == r:
        r += 1
    else:
        xor_A -= A[l]
print(ans)
### BUGGY CODE ###

from fractions import gcd
from functools import reduce

mod = 10 ** 9 + 7

def lcm(a,b):
    return a * b//gcd(a,b)

n = int(input())
lis = list(map(int,input().split()))
now = reduce(lcm,lis)

num = list(map(lambda x:now//x,lis))

print(sum(num) % mod)


### FIXED CODE ###

from fractions import gcd
from functools import reduce

mod = 10 ** 9 + 7

def lcm(a,b):
    return a * b//gcd(a,b)

n = int(input())
lis = list(map(int,input().split()))
now = reduce(lcm,lis)

print(sum(list(map(lambda x:now//x,lis)))%mod)
### BUGGY CODE ###

import numpy as np
import math
import collections

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

ans = 1
for a in A:
    ans *= a

if ans > 10**18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

import numpy as np
import math
import collections

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

ans = 1
if 0 in A:
    print(0)
    exit()
for a in A:
    ans *= a
    if ans > 10**18:
        print(-1)
        exit()

if ans > 10**18:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import time
N, K = list(map(int, input().split()))
H = list(map(int, input().split()))

cost = [0] * N
cost[0] = 0
for n in range(1, N):
  # t = time.time()
  cost[n] = min([ cost[n-k]+abs(H[n-k]-H[n]) for k in range(1, min(n+1, K+1)) ])
  # print(time.time()-t)
print(cost[-1])

### FIXED CODE ###

#  def II(): return int(input())
#def LI(): return [int(i) for i in input().split()]

#N, K = LI()
#H = LI()

#cost = [0] * N
#cost[0] = 0
#for n in range(1, N):
#  cost[n] = min([ cost[n-k]+abs(H[n-k]-H[n]) for k in range(1, min(n+1, K+1)) ])

#print(cost[-1])

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    a = [0] * n
    a[0] = 0
    for i in range(1, n):
        a[i] = min([a[j] + abs(h[i] - h[j]) for j in range(max(0, i - k), i)])
    print(a[-1])
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N,Q=(int(i) for i in input().split())
x=input()
a=[]

j=0
s=[]
while (j<len(x)-1):
  if (x[j]=="A"):
    if (x[j+1]=="C"):
      s.append(j+1)
      j+=1
  j+=1
for i in range(0,Q):
  if s==[]:
    print(0)
    continue
  a.append([int(j) for j in input().split()])
  answer=0
  j=0
  while s[j]<a[i][0]:
    j+=1
    if len(s)<=j:break
  k=0
  while s[k]<a[i][1]:
    k+=1
    if len(s)<=k:break
  print(k-j)




### FIXED CODE ###

N,Q=(int(i) for i in input().split())
x=input()
a=[]

j=0
s=[0]
t=0
while (j<N-1):
  if (x[j]=="A") and (x[j+1]=="C"):
    t+=1
    s.append(t)
  else:s.append(t)
  j+=1
for i in range(0,Q):
  a.append([int(j) for j in input().split()])
  p=s[a[i][1]-1]-s[a[i][0]-1]
  print(p)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

N = int(input())
A_list = list(map(int, input().split()))
ans = 0
SUM = sum(A_list)
for i in range(N):
    SUM -= A_list[i]
    if i != N -1:
        ans += A_list[i] * SUM
while ans >= 10 ** 17 + 700000000:
    ans -= 10 ** 17 + 700000000
while ans >= 10 ** 15 + 7000000:
    ans -= 10 ** 15 + 7000000
while ans >= 10 ** 13 + 70000:
    ans -= 10 ** 13 + 70000
while ans >= 10 ** 11 + 700:
    ans -= 10 ** 11 + 700
while ans >= 10 ** 9 + 7:
    ans -= 10 ** 9 + 7
print(ans)


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

N = int(input())
A_list = list(map(int, input().split()))
ans = 0
SUM = sum(A_list)
for i in range(N):
    SUM -= A_list[i]
    if i != N -1:
        ans += A_list[i] * SUM
while ans >= 10 ** 21 + 7000000000000:
    ans -= 10 ** 21 + 7000000000000
while ans >= 10 ** 19 + 70000000000:
    ans -= 10 ** 19 + 70000000000
while ans >= 10 ** 17 + 700000000:
    ans -= 10 ** 17 + 700000000
while ans >= 10 ** 15 + 7000000:
    ans -= 10 ** 15 + 7000000
while ans >= 10 ** 13 + 70000:
    ans -= 10 ** 13 + 70000
while ans >= 10 ** 11 + 700:
    ans -= 10 ** 11 + 700
while ans >= 10 ** 9 + 7:
    ans -= 10 ** 9 + 7
print(ans)
### BUGGY CODE ###

import itertools
n=int(input())
s = []
for _ in range(n):
    s.append(input())
#print(s)
#s = list(itertools.chain.from_iterable(s))
#print(s)
s_u = list(set(s))
box = []
for i in range(len(s_u)):
    box.append([s_u[i],s.count(s_u[i])])
count=1
box = sorted(box,key=lambda x:x[1],reverse=True)
#print(box)
for i in range(len(s_u)-1):
    if len(box)==1:
      break
    elif box[i][1] == box[i+1][1]:
        count+=1
    elif box[i][1] > box[i+1][1]:
        break
box_p = [box[i] for i in range(count)]
#print(box_p)
ans_box = sorted(box_p)
for i in range(count):
    print(ans_box[i][0])

### FIXED CODE ###

n=int(input())
dic = dict()

a = 0
for i in range(n):
    s = str(input())
    if s in dic:
        dic[s] += 1
    else:
        dic[s] = 1
    if dic[s] > a:
        a = dic[s]
box= []
for i in dic:
    if dic[i] == a:
        box.append(i)

ans = sorted(box)
for i in range(len(ans)):
    print(ans[i])
### BUGGY CODE ###

import math

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

maxresult = 0


#for x in range(n+1):
#    if (a * x * 1.0 // b) - a * (x * 1.0 // b) >= maxresult:
#        maxresult = int((a * x * 1.0 // b) - a * (x * 1.0 // b))

for x in range(n+1):
    if a * math.modf(x*1.0/b)[0] >= maxresult:
        maxresult = a * math.modf(x*1.0/b)[0]

print(int(maxresult))

### FIXED CODE ###

import math

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

maxresult = 0

#これはタイムオーバー
#for x in range(n+1):
#    if (a * x * 1.0 // b) - a * (x * 1.0 // b) >= maxresult:
#        maxresult = (a * x * 1.0 // b) - a * (x * 1.0 // b)

#これもタイムオーバー
#for x in range(n+1):
#    if a * math.modf(x*1.0/b)[0] >= maxresult:
#        maxresult = a * math.modf(x*1.0/b)[0]

"""
解説動画を見て、再考
x = pB + qと変形する。（https://twitter.com/chokudai/status/1256806061194874881）
floor[Ax / B]
=floor[(APB+Aq) / B]
=Ap + floor[Aq / B]

A * floor[x / B]
= A * floor[(pB+q) / B]
= A * (p + floor[q/B])

よって、
floor[Ax / B] - A * floor[x / B]
=Ap + floor[Aq / B] - Ap - A * floor[q / B]
=floor[Aq / B] - A * floor[q / B]
  #x = pB + qであるため、floor[q/B] = 0
=floor[Aq / B]
  #q = (x % B)なので
=floor[A/B * (x % B)]
この値が最大になればよく、xは整数なので、
x = B-1の時が最大となる。

ただしN < B-1の場合は、x = B-1を取れないので、
そのときにはxの最大値x=Nとなる。
"""

if n < b-1:
    x = n
else:
    x = b-1
maxresult = a * (x%b) // b

print(int(maxresult))
### BUGGY CODE ###

import re
S = input()
counter = 0
ans_bf = len(S)
while True:
    len_bf = len(S)
    S = re.sub(r"01","",S)
    S = re.sub(r"10","",S)
    if len_bf == len(S):
        break
print(ans_bf - len(S))


### FIXED CODE ###

import collections
S = input()
col_S = collections.Counter(S) 
print(min(col_S['0'],col_S['1'])*2)
### BUGGY CODE ###

n, x, y = map(int, input().split())

lis = [0]*(n-1)
for i in range(n):
    for j in range(i+1, n):
        a = j-i
        b = min(abs(x-1-i), abs(y-1-i)) + 1 + min(abs(y-1-j), abs(x-1-j))
        dist = min(a, b)
        lis[dist-1] += 1

for i in lis:
    print(i)

### FIXED CODE ###

n, x, y = map(int, input().split())

lis = [0]*(n-1)
for i in range(n):
    disxi = min(abs(x-1-i), abs(y-1-i))
    for j in range(i+1, n):
        a = j-i
        if a == 1:
            dist = 1
        else:
            b = disxi + 1 + min(abs(y-1-j), abs(x-1-j))
            dist = min(a, b)
        lis[dist-1] += 1

for i in lis:
    print(i)
### BUGGY CODE ###

K, S = map(int, input().split())

ans = 0
for x in range(K+1):
    for y in range(K+1):
        if x + y > S:
            break
        for z in range(K+1):
            if x + y + z > S:
                break

            if x + y + z == S:
                ans += 1

print(ans)

### FIXED CODE ###

K, S = map(int, input().split())

ans = 0
for x in range(K+1):
    for y in range(K+1):
        x_y = x + y
        if x_y > S:
            break
        if S - x_y <= K:
            ans += 1

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

S = input()
ret = 0
counter = {0: 1}
for i in range(len(S)):
    mod = int(S[-i:]) % 2019
    if mod in counter:
        counter[mod] += 1
    else:
        counter[mod] = 1
for k, v in counter.items():
    ret += v * (v - 1) // 2

print(ret)

### FIXED CODE ###

from collections import Counter

S = input()
mods = [0]
num, ten = 0, 1
for n in S[::-1]:
    num += int(n) * ten
    num %= 2019
    mods.append(num)
    ten *= 10
    ten %= 2019

counter = Counter(mods)
ret = 0
for v in counter.values():
    ret += v * (v - 1) // 2
print(ret)
### BUGGY CODE ###

N = int(input())
b = 10**9+7
A = list((int(x)%b for x in input().split()))
ans = 0
for i in range(N-1):
  for j in range(i+1,N):
    ans += (A[i]*A[j]) % b
print(ans % b)

### FIXED CODE ###

N = int(input())
b = 10**9+7
A = list((int(x) for x in input().split()))
sum = 0
for a in A:
  sum += a
ans = 0
for i in range(N-1):
  sum -= A[i]
  ans += A[i]*sum
print(ans % b)
### BUGGY CODE ###

n,m=map(int, input().split())
ko=[[] for i in range(n)]
oya=[[] for i in range(n)]
rank=[0]*n 
for i in range(n-1+m):
    a,b=map(int, input().split())
    ko[b-1].append(a-1)
    oya[a-1].append(b-1)
from collections import deque
s=0
for i in range(n):
    if len(ko[i])==0:s=i
p=deque([s])
nr=1
ans=[0]*n
while p:
    now=p.popleft()
    nr=rank[now]+1
    p.extend(oya[now])
    for i in oya[now]:
        rank[i]=nr
        ans[i]=now+1
for i in ans:print(i)

### FIXED CODE ###

n,m=map(int,input().split())
oya=[set() for i in range(n)]
ko=[set() for i in range(n)]
rank=[0]*n
for i in range(n+m-1):
    a,b=map(int,input().split())
    ko[a-1].add(b-1)
    oya[b-1].add(a-1)
for s in range(n):
    if not oya[s]:break
q=[[s,ko[s]]]
ans=[0]*n
while q:
    now,nex=q.pop()
    for i in nex:
        oya[i].remove(now)
        if not oya[i]:
            ans[i]=now+1
            q.append([i,ko[i]])
for i in ans:print(i)
### BUGGY CODE ###


N = int(input())

uvw = []
Nlis = [-1] * N
Ndic = {}

for i in range(N-1):

    u,v,w = map(int,input().split())
    
    if u not in Ndic:
        Ndic[u] = [[v,w]]

    else:
        Ndic[u].append([v,w])

    if v not in Ndic:
        Ndic[v] = [[u,w]]

    else:
        Ndic[v].append([u,w])


ends = [1]
Q = [1]
Nlis[0] = 0

while len(Q) > 0:

    now = Q.pop(0)

    for nw in Ndic[now]:

        if nw[0] not in ends:

            Q.append(nw[0])
            ends.append(nw[0])

            if nw[1] % 2 == 0:
                Nlis[nw[0]-1] =  Nlis[now-1]

            else:
                Nlis[nw[0]-1] = (Nlis[now-1] + 1) % 2

for i in Nlis:
    print(i)


### FIXED CODE ###


N = int(input())

uvw = []
Nlis = [-1] * N
Ndic = {}

for i in range(N-1):

    u,v,w = map(int,input().split())
    
    if u not in Ndic:
        Ndic[u] = [[v,w]]

    else:
        Ndic[u].append([v,w])

    if v not in Ndic:
        Ndic[v] = [[u,w]]

    else:
        Ndic[v].append([u,w])


ends = set([1])
Q = [1]
Q_cnt = 0
Nlis[0] = 0

while len(Q) > Q_cnt and N != 1:

    now = Q[Q_cnt]
    Q_cnt += 1

    for nw in Ndic[now]:

        if nw[0] not in ends:

            Q.append(nw[0])
            ends.add(nw[0])

            if nw[1] % 2 == 0:
                Nlis[nw[0]-1] =  Nlis[now-1]

            else:
                Nlis[nw[0]-1] = (Nlis[now-1] + 1) % 2

            #Ndic[nw[0]].remove([now,nw[1]])

for i in Nlis:
    print(i)
### BUGGY CODE ###


N = int(input())

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

A.sort(reverse=True)
ans = A.pop(0)
N -= 2

while N > 0:
    if N >= 2:
        ans += A.pop(0)*2
        N -= 2
    else:
        ans += A.pop(0)
        N -= 1

print(ans)

### FIXED CODE ###


N = int(input())

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

A.sort(reverse=True)
ans = A.pop(0)
N -= 2
n = N//2
if N % 2 == 0:
    ans += 2 * sum(A[:n])
else:
    ans += 2 * sum(A[:n])
    ans += A[n]

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

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

ans = 1
for a in A:
    ans *= a

if ans > 10**18:
    print('-1')
    exit()

print(ans)


### FIXED CODE ###

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

ans = 1
if 0 in A:
    print(0)
    exit()
for a in A:
    ans *= a
    if ans > 10**18:
        print('-1')
        exit()

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

def main():
    a = {j: i for i, j in enumerate('abcdefghijklmnopqrstuvwxyz')}
    S = [a[i] for i in input()]
    n = len(S)
    dp = [0]*(n+1)

    parity = 0
    dict_parity = {0: 0}

    for i, s in enumerate(S):
        parity ^= 2**s
        ans = i+1
        if parity not in dict_parity:
            dict_parity[parity] = i+1
        else:
            ans = min(ans, dp[dict_parity[parity]]+1)
        for j in range(26):
            parity2 = parity ^ 2**j
            if parity2 in dict_parity:
                ans = min(ans, dp[dict_parity[parity2]]+1)
        dp[i+1] = ans
        if dict_parity[parity] > ans:
            dict_parity[parity] = i+1
    print(dp[-1])


main()

### FIXED CODE ###

def main():
    S = input()
    n = len(S)
    a = {j: i for i, j in enumerate('abcdefghijklmnopqrstuvwxyz')}
    S = [a[i] for i in S]
    dp = [10**9]*(n+1)
    dp[0] = 0

    parity = 0
    dict_parity = {0: 0}

    for i, s in enumerate(S):
        parity ^= 2**s
        ans = i+1
        if parity not in dict_parity:
            dict_parity[parity] = i+1
        else:
            ans = min(ans, dp[dict_parity[parity]]+1)
        for j in range(26):
            parity2 = parity ^ 2**j
            if parity2 in dict_parity:
                ans = min(ans, dp[dict_parity[parity2]]+1)
        dp[i+1] = ans
        if dict_parity[parity] > ans:
            dict_parity[parity] = i+1
    print(dp[-1])


main()
### BUGGY CODE ###

N=int(input())
AN=[int(input()) for _ in range(N)]

for i in range(N):
    tmp=AN.copy()
    tmp.pop(i)
    print(max(tmp))

### FIXED CODE ###

N=int(input())
AN=[int(input()) for _ in range(N)]
ret=max(AN)
ANc=sorted(AN,reverse=True)
ret2=ANc[1]

for i in range(N):
    if ret != AN[i]:
        print(ret)
    else:
        print(ret2)
### BUGGY CODE ###

from collections import deque
h,w=map(int,input().split())
ch,cw=map(lambda x:int(x)-1,input().split())
dh,dw=map(lambda x:int(x)-1,input().split())
tizu=[]
d=deque()
d.appendleft([ch,cw])
cost=[[-1 for i in range(w)]for j in range(h)]
dx=[1,0,-1,0,-2,-2,-2,-2,-2,-1,-1,-1,-1,0,0,1,1,1,1,2,2,2,2,2]
dy=[0,1,0,-1,-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]
for i in range(h):
    tizu.append(input())
cost[ch][cw]=0
while(d):
    x,y=d.popleft()
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        ####行ったことある、かつ、コストが手前より高い
        if(nx<0 or ny<0 or nx>=h or ny>=w):
            continue
        if(cost[nx][ny]>-1 and cost[nx][ny]<=cost[x][y]):
            continue
        if(tizu[nx][ny]=='.'):
            cost[nx][ny]=cost[x][y]
            d.appendleft([nx,ny])
    
    for i in range(4,24):
        nx=x+dx[i]
        ny=y+dy[i]
        if(nx<0 or ny<0 or nx>=h or ny>=w):
            continue
        if(cost[nx][ny]>-1 and cost[nx][ny]<=cost[x][y]):
            continue
        if(tizu[nx][ny]=='.'):
            cost[nx][ny]=cost[x][y]+1
            d.append([nx,ny])

print(cost[dh][dw])

### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
ch,cw=map(lambda x:int(x)-1,input().split())
dh,dw=map(lambda x:int(x)-1,input().split())
tizu=[]
d=deque()
d.appendleft([ch,cw])
cost=[[-1 for i in range(w)]for j in range(h)]
dx=[1,0,-1,0,-2,-2,-2,-2,-2,-1,-1,-1,-1,0,0,1,1,1,1,2,2,2,2,2]
dy=[0,1,0,-1,-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]
for i in range(h):
    tizu.append(input())
cost[ch][cw]=0
while(d):
    x,y=d.popleft()
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        ####行ったことある、かつ、コストが手前より高い
        if(nx<0 or ny<0 or nx>=h or ny>=w):
            continue
        if(cost[nx][ny]>-1 and cost[nx][ny]<=cost[x][y]):
            continue
        if(tizu[nx][ny]=='.'):
            cost[nx][ny]=cost[x][y]
            d.appendleft([nx,ny])
    
    for i in range(4,24):
        nx=x+dx[i]
        ny=y+dy[i]
        if(nx<0 or ny<0 or nx>=h or ny>=w):
            continue
        if(cost[nx][ny]>-1):
            continue
        if(tizu[nx][ny]=='.'):
            cost[nx][ny]=cost[x][y]+1
            d.append([nx,ny])

print(cost[dh][dw])
### BUGGY CODE ###

import math
K = int(input())
ans =0
def koyakusu(A,B,C):
  kotae = math.gcd(A,B)
  kotae = math.gcd(kotae,C)
  return kotae
  
  
for a in range(1,K+1):
  for b in range(1,K+1):
    for c in range(1,K+1):
      ans +=koyakusu(a,b,c)

print(ans)

### FIXED CODE ###

import math
K = int(input())+1
ans=0
for a in range(1,K):
  for b in range(1,K):
    gcdab = math.gcd(a,b)
    for c in range(1,K):
      ans += math.gcd(gcdab,c)

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

from collections import Counter
from bisect import bisect_left

N = int(input())
A = list(map(int, input().split()))
a = list(Counter(A).values())
a.sort()
s = sum(a)

for i in range(1, N + 1):
    if i == 1:
        print(s)
    elif len(a) < i:
        print(0)
    else:
        n = s // i
        for j in reversed(range(1, n + 1)):
            t = bisect_left(a, j)
            if j * i <= sum(a[:t]) + (len(a) - t) * j:
                print(j)
                break

### FIXED CODE ###

from collections import Counter
from bisect import bisect_left
from itertools import accumulate

N = int(input())
A = list(map(int, input().split()))
a = list(Counter(A).values())
a.sort()
b = list(accumulate(a + [0]))
s = sum(a)
length = len(a)

for i in range(1, N + 1):
    if i == 1:
        print(s)
    elif len(a) < i:
        print(0)
    else:
        n = s // i
        for j in reversed(range(1, n + 1)):
            t = bisect_left(a, j)
            if j * i <= b[t - 1] + (length - t) * j:
                print(j)
                break
### BUGGY CODE ###

A, B, N = list(map(int, input().split()))
def function(a, b, x):
  return (a*x)//b - a*(x//b)
print(max([function(A, B, i) for i in range(max([1, N-B]), N+1)]))

### FIXED CODE ###

A, B, N = list(map(int, input().split()))
def function(a, b, x):
  return (a*x)//b - a*(x//b)
print(max([function(A, B, N), function(A, B, max([1, N-N%B-1]))]))
### BUGGY CODE ###

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

def kitai(x):
	sum = x*(1+x)/2
	return sum/x

max=0
for i in range(n-k+1):
	sum=0
	for j in range(k):
		sum+=kitai(p[i+j])
	if sum>max:
		max=sum
	
print(max)	

### FIXED CODE ###

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

E=[0]*n #期待値=E[i]
S=[0]*(n+1) #累積和=S[i+1]=E[0]+E[1]+...+E[i](S[0]=0)

for i in range(n):
	E[i]=(1+P[i])/2
	S[i+1]=S[i]+E[i]
max=0
for i in range(k,n+1):
	if S[i]-S[i-k] > max:
		max=S[i]-S[i-k]
print(max)