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

#!/usr/bin/env python3
import sys
from collections import deque
from math import inf


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


def bfs(maze, Ch, Cw, Dh, Dw, H, W):
    visited = [[inf] * W for i in range(H)]
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    dy_dx0 = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    dy_dx1 = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2],
              [0, -2], [-1, 2], [-1, 1], [-1, -1], [-1, -2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]]

    while queue:
        y, x = queue.popleft()
        if [y, x] == [Dh, Dw]:
            break
        for j, k in dy_dx0:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[y][x] < visited[new_y][new_x]:
                    visited[new_y][new_x] = visited[y][x]
                    queue.appendleft([new_y, new_x])
        for j, k in dy_dx1:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[new_y][new_x] == inf:
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])
    return visited[Dh][Dw]


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    maze = [input() for i in range(H)]

    dist = bfs(maze, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)
    
    print(dist if dist != inf else -1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque
from math import inf


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


def bfs(maze, Ch, Cw, Dh, Dw, H, W):
    visited = [[inf] * W for i in range(H)]
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    dy_dx0 = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    dy_dx1 = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2],
              [0, -2], [-1, 2], [-1, 1], [-1, -1], [-1, -2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]]

    while queue:
        y, x = queue.popleft()
        if [y, x] == [Dh, Dw]:
            break
        for j, k in dy_dx0:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[y][x] < visited[new_y][new_x]:
                visited[new_y][new_x] = visited[y][x]
                queue.appendleft([new_y, new_x])
        for j, k in dy_dx1:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[new_y][new_x] == inf:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
    return visited[Dh][Dw]


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    maze = [input() for i in range(H)]

    dist = bfs(maze, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)

    print(dist if dist != inf else -1)


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

N = int(input())
P = list(map(int, input().split()))
count = 0
for i in range(N):
  if P[i] == min(P[:i+1]):
    count += 1
print(count)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
count = 1
m = P[0]
for i in range(1, N):
  if P[i] < m:
    m = P[i]
    count += 1
print(count)
### BUGGY CODE ###

import sys
from bisect import *

input = sys.stdin.readline

def f(n, q):
    xst = []
    for i in range(n):
        s, t, x = map(int, input().split())
        xst.append([x, s - x, t - x])
    xst.sort()

    ds = []
    ans = [-1] * q
    for i in range(q):
        d = int(input())
        ds.append(d)

    for x, s, t in xst:
        i = bisect_left(ds, s)
        while i < q:
            if ds[i] < t:
                if ans[i] == -1:
                    ans[i] = x
                i += 1
            else:
                break

    print(*ans, sep="\n")

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


### FIXED CODE ###

import sys
from bisect import *

input = sys.stdin.readline

def f(n, q):
    xst = []
    for i in range(n):
        s, t, x = map(int, input().split())
        xst.append([x, s - x, t - x])
    xst.sort()

    ds = []
    for i in range(q):
        d = int(input())
        ds.append(d)

    ans = [-1] * q
    jump = [-1] * q

    for x, s, t in xst:
        i = bisect_left(ds, s)
        fi = bisect_left(ds, t)
        while i < fi:
            if jump[i] != -1:
                i = jump[i]
            else:
                ans[i] = x
                jump[i] = fi
                i += 1

    print(*ans, sep="\n")

n, q = map(int, input().split())
f(n, q)
### BUGGY CODE ###

import sys
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3
#sys.setrecursionlimit(int(1e+6))
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))
MOD = int(1e+9) + 7

def main():
    N, Q = i2nn()
    STX = ii2nnn(N) # 座標 X で時刻 [S, T) が工事
    D = ii2nn(Q)    # 昇順ソート済み
    E = [-1] * Q
    STX.sort(key=lambda v: v[2])
    for s, t, x in STX:
        a = bisect_left(D, s-x)
        b = bisect_left(D, t-x)
        for i in range(a, b):
            if E[i] == -1:
                E[i] = x
    for e in E:
        print(e)

main()


### FIXED CODE ###

import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop

print('\n'.join(map(str, ans)))
### BUGGY CODE ###

target = int(input())
ans = 0
waru = 2
while target >= waru:
  if target % waru == 0:
    for i in range(2, waru + 1):
      if waru % i == 0:
        waruwaru = i
        break
    waru_copy = waru
    while waru_copy != 1:
      if waru_copy % waruwaru == 0:
        waru_copy /= waruwaru
      else:
        break
    else:
      target /= waru
      ans += 1
  waru += 1
print(ans)


### FIXED CODE ###

target = int(input())
num = target
waru = 2
exp = []
while waru ** 2 <= target and num > 1:
    rep = 0
    while num % waru == 0:
        num /= waru
        rep += 1
    waru += 1
    if rep > 0:
        exp.append(rep)
if num > 1:
    exp.append(1)
ans = 0
for item in exp:
    hiku = 1
    while item - hiku >= 0:
        item -= hiku
        ans += 1
        hiku += 1
print(ans)
### BUGGY CODE ###

X = int(input())

def get_change(pay):
    for n in range(6):
        if pay%(100+n) == 0:
            print(1)
            exit(0)
        if pay > 100+n:
            get_change(pay-100-n)
    return 2
res = get_change(X)
if res == 2:
    print(0)


### FIXED CODE ###

X = int(input())
N = X//100
pay = X-N*100
if pay/5 > N:
    print(0)
else:
    print(1)
### BUGGY CODE ###

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

Ans = 0

for x in range(K+1):
	for y in range(K+1):
		for z in range(K+1):
			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):
		if 0 <= S - x - y <= K:
			Ans += 1

print(Ans)
### BUGGY CODE ###

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

S.sort()
items = 0
i = 0

while i < N:
    items += 1
    for j in range(i+1, N):
        if S[i] == S[j]:
            i += 1
    i += 1

print(items)
       

### FIXED CODE ###

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

print(len(set(S)))
### BUGGY CODE ###

# ソートしたやつの小さい方から2つを決めてもうひとつはにぶたん
# 3, 5としたときに残りの一つは5, 6, 7みたいになる
# このにぶたんなんか実装がめっっっちゃむずくない？サンプル1が通らんのだが

import bisect

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


def lower_bound(arr, x):
    l, r = 0, len(arr)
    while l < r:
        mid = (l + r) // 2
        if arr[mid] < x:
            l = mid + 1
        else:
            r = mid
    return l


ans = 0
for i in range(n - 2):
    for j in range(i + 1, n - 1):
        idx_l = lower_bound(arr, arr[i] + arr[j]) - 1
        # print(
        #     "arr[{}]+arr[{}]={}より小さくなるはじめてのインデックス {}".format(
        #         i, j, arr[i] + arr[j], idx_l
        #     )
        # )
        # print("idx_l = {}, arr[{}]={}".format(idx_l, idx_l, arr[idx_l]))
        # print("範囲 {}".format(arr[j + 1 : idx_l + 1]))
        ans += len(arr[j + 1 : idx_l + 1])
print(ans)


### FIXED CODE ###

# ソートしたやつの小さい方から2つを決めてもうひとつはにぶたん
# 3, 5としたときに残りの一つは5, 6, 7みたいになる
# このにぶたんなんか実装がめっっっちゃむずくない？サンプル1が通らんのだが
# やったけどTLEなるな

import bisect

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


def lower_bound(arr, x):
    l, r = 0, len(arr)
    while l < r:
        mid = (l + r) // 2
        if arr[mid] < x:
            l = mid + 1
        else:
            r = mid
    return l


ans = 0
for i in range(n - 2):
    for j in range(i + 1, n - 1):
        idx_l = lower_bound(arr, arr[i] + arr[j]) - 1
        # print(
        #     "arr[{}]+arr[{}]={}より小さくなるはじめてのインデックス {}".format(
        #         i, j, arr[i] + arr[j], idx_l
        #     )
        # )
        # print("idx_l = {}, arr[{}]={}".format(idx_l, idx_l, arr[idx_l]))
        # print("範囲 {}".format(arr[j + 1 : idx_l + 1]))
        ans += len(arr[j + 1 : idx_l + 1])
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

#import
#import math
#import numpy as np
#= int(input())
#= input()
modnum = 998244353

N, K = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(K)]

def mod(num):
    return num % modnum

S = []

for l, r in LR:
    for i in range(l, r + 1):
        if not i in S:
            S.append(i)

dp = [0] * N

dp[0] = 1

for i in range(1, N):
    for s in S:
        if not s > i:
            dp[i] = mod(dp[i] + dp[i - s])

print(dp[N-1])



### FIXED CODE ###

#!/usr/bin/env Python3

#import
#import math
#import numpy as np
#= int(input())
#= input()
modnum = 998244353

N, K = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(K)]

def mod(num):
    return num % modnum

dp = [0] * (N + 1)
sdp = [0] * (N + 1)

dp[1] = 1
sdp[1] = 1

for i in range(2, N + 1):
    for l, r in LR:
        ri = max(0, i - l)
        li = max(0, i - r - 1)

        dp[i] += sdp[ri] - sdp[li]
        dp[i] = mod(dp[i])

    sdp[i] = sdp[i - 1] + dp[i]

print(dp[N])
### BUGGY CODE ###

h, w, k = map(int, input().split())
s = [input() for _ in range(h)]

minimum = (h - 1) * (w - 1)
for div_h in range(1 << (h - 1)):
  h_index = [0] * h
  cur_index = 0
  mask = 1 << (h - 2)
  for i in range(1, h):
    if div_h & mask:
      cur_index += 1
    h_index[i] = cur_index
    mask >>= 1
  white_choco = [0] * (cur_index + 1)
  divide = 0
  j = 0
  while j < w:
    for i in range(h):
      if s[i][j] == '1':
        if white_choco[h_index[i]] < k:
          white_choco[h_index[i]] += 1
        else:
          break
    else:
      j += 1
      continue
    white_choco = [0] * (cur_index + 1)
    divide += 1
  minimum = min(minimum, divide + cur_index)
print(minimum)

### FIXED CODE ###

h, w, k = map(int, input().split())
s = [[int(s_ij) for s_ij in input()] for _ in range(h)]

minimum = (h - 1) * (w - 1)
for div_h in range(1 << (h - 1)):
  h_index = [0] * h
  cur_index = 0
  mask = 1 << (h - 2)
  for i in range(1, h):
    if div_h & mask:
      cur_index += 1
    h_index[i] = cur_index
    mask >>= 1
  white_choco = [0] * (cur_index + 1)
  divide = 0
  j = 0
  flag = False
  while j < w:
    for i in range(h):
      white_choco[h_index[i]] += s[i][j]
    if max(white_choco) > k:
      if flag:
        break
      flag = True
      white_choco = [0] * (cur_index + 1)
      divide += 1
    else:
      j += 1
      flag = False
  else:
    minimum = min(minimum, divide + cur_index)
print(minimum)
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate
import math

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    mina = min(A)
    for i in range(K):
        B = [0]*N
        for j in range(N):
            if j-A[j] >= 0:
                B[j-A[j]] += 1
            else:
                B[0] += 1
            if j+A[j]+1 < N:
                B[j+A[j]+1] -= 1
            # print(j,B)
        A = list(accumulate(B[:]))
        mina = mina*2+1
        if mina >= N and A[0] == A[-1] == N:
            break
        # print(A,mina) 
    print(*A)

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate
import math

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    mina = min(A)
    for i in range(K):
        B = [0]*N
        for j in range(N):
            if j-A[j] >= 0:
                B[j-A[j]] += 1
            else:
                B[0] += 1
            if j+A[j]+1 < N:
                B[j+A[j]+1] -= 1
        A = list(accumulate(B[:]))
        mina = mina*2+1
        if mina >= N and A[0] == A[-1] == N:
            break
    print(*A)

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

# E - Flatten

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

modulus = 10 ** 9 + 7

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

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

l = 1
for x in a:
    l = lcm(l, x)

s = sum((l // x) % modulus for x in a)
print(s % modulus)


### FIXED CODE ###

# E - Flatten

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

modulus = 10 ** 9 + 7
binmod = (bin(modulus - 2))[2:]  # modulus - 2 in binary

MAX = 10 ** 6

primefact = [0 for i in range(MAX + 1)]

def sieve():
    # cf. https://www.geeksforgeeks.org/lcm-of-n-numbers-modulo-m/
    for i in range(2, MAX + 1):
        if primefact[i] == 0:
            for j in range(i, MAX + 1, i):
                if primefact[j] == 0:
                    primefact[j] = i

def factorize(x):
    if primefact[2] == 0:
        sieve()

    vec = {}
    while x >= 2:
        d = primefact[x]
        if d not in vec:
            vec[d] = 0
        vec[d] += 1
        x //= d
    return vec

def value(x):
    p = 1
    for i in x:
        p = (p * (i ** x[i])) % modulus
    return p

def inverse(x):
    p = 1
    for b in binmod:
        p = p * p % modulus
        if b == '1':
            p = p * x % modulus
    return p

def div(n, d):
    return n * inverse(d) % modulus

fact = [factorize(x) for x in a]

fset = set()
for f in fact:
    fset.update(f.keys())

l = {k: 0 for k in fset}
for f in fact:
    for k in f:
        l[k] = max(l[k], f[k])
lcm = value(l)

s = sum(div(lcm, x) for x in a) % modulus
print(s)
### BUGGY CODE ###

import math
import sys
input = sys.stdin.readline
a,b,n = map(int,input().split())
li = []

for x in range(n+1):
    li.append(int((a*(x))/b) - a * int(x/b))
print(max(li))

### FIXED CODE ###

import math
 
A, B, N = map(int, input().split())
 
 
ans1 = 0
 
if N > B - 1:
    x = B-1
    print(int((A * x) / B) - A * int(x / B))
elif N <= B - 1:
    x = N
    print(int((A * x) / B) - A * int(x / B))
### BUGGY CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
ans = 0

if(n <= k):
  print(0)
else:
  if(k == 0):
    print(sum(h))
  elif(int(n/2) <= k):
    for i in range(n-k):
      min_h = min(h)
      h[h.index(min_h)] = 10**18
      ans = ans + min_h
    print(ans)
  else:
    for i in range(k):
      max_h = max(h)
      h[h.index(max_h)] = 0
      print(sum(h))

### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
ans = 0

if(n <= k):
  print(0)
else:
  h.sort()
  a = []
  a = h[:n-k]
  print(sum(a))
### BUGGY CODE ###

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

while True:
    t = max(arr) % min(arr)
    if t == 0:
        arr.pop(arr.index(max(arr)))
    else:
        arr[arr.index(max(arr))] = t
    
    if len(arr) == 1:
        print(min(arr))
        break

### FIXED CODE ###

n = int(input())
b = list(map(int,input().split()))
b.sort()
     
d = b[0] + 0
 
while len(b) > 1 :
    for i in range(1,len(b)) :
        b[i] = b[i] % b[0]
    if b.count(0) == len(b)-1 :
        d = b[0]
        break
    else :
        b.sort()
        for j in range(b.count(0)) :
            b.remove(0)
print(d)
### BUGGY CODE ###

#import sys
#input = sys.stdin.readline
def main():
    L, A, B, M = map( int, input().split())
    s = A
    ans = 0
    for _ in range(L):
        ans = (ans*pow(10, len( str(s)), M) + s )%M
        s += B
    print(ans)
if __name__ == '__main__':
    main()


### FIXED CODE ###

#import sys
#input = sys.stdin.readline
#from numpy import matrix, eye, dot
def productMatrix(N, A, B):
    Ret = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                Ret[i][j] += A[i][k]*B[k][j]
    return Ret
def modMatrix(N, A, Q): #N×N行列のmod
    for i in range(N):
        for j in range(N):
            A[i][j] %= Q
#            A[i,j] %= Q
    return

def powOfMatrix(N, X, n, Q): #N×N行列のn乗
#    Ret = eye(N)
    Ret = [[1,0,0],[0,1,0],[0,0,1]]
    power = '{:060b}'.format(n)[::-1] #log2(pow(10,18)) < 60
    for p in power:
        if p == "1":
            Ret = productMatrix(N,Ret, X)
#            Ret = dot(Ret, X)
            modMatrix(N, Ret, Q)
        X = productMatrix(N,X,X)
#        X = dot(X,X)
        modMatrix(N, X, Q)
#        print(Ret)
    return Ret

def main():
    L, A, B, M = map( int, input().split())
    s = A
    ANS = [[1,0,0],[0,1,0],[0,0,1]]
    for i in range(1, 37):
#        print(i, ANS)
        if s >= pow(10,i):
            continue
        P = [[pow(10, i, M), 0, 0], [1,1,0], [0,B,1]]
#        P = matrix([[pow(10, i, M), 0, 0], [1,1,0], [0,B,1]])
#        print((pow(10,i)-1-s)//B+1)
        step = (pow(10,i)-s+B-1)//B
        if L <= step:
            ANS = productMatrix(3,ANS,powOfMatrix(3,P,L,M))
#            ANS = dot(ANS,powOfMatrix(3,P,L,M))
            modMatrix(3,ANS,M)
            break
#        print(powOfMatrix(3,P, (pow(10,i)-1-s)//B + 1,M))
        ANS = productMatrix(3,ANS, powOfMatrix(3,P, step,M))
#        ANS = dot(ANS, powOfMatrix(3,P, (pow(10,i)-1-s)//B + 1,M))
#        print( (ANS[1][0]*A + ANS[2][0])%M, (pow(10,i)-1-s)//B + 1)
        modMatrix(3,ANS, M)
        L -= step
        s += step*B
    print( (ANS[1][0]*A + ANS[2][0])%M)
#    print( int((ANS[1,0]*A + ANS[2,0])%M))
        
        
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import fractions
K = int(input())

i=0
dammy=[0]*(K*K*K)
for a in range(1,K+1):
    for b in range(1,K+1):
        f=fractions.gcd(a,b)
        for c in range(1,K+1):


            ff = fractions.gcd(f,c)
            #dammy.append(ff)
            dammy[i]=ff
            i+=1

print(sum(dammy))

### FIXED CODE ###

import fractions
K = int(input())

gcd = [[0]*K for i in range(K)]
L = [0]*K

for a in range(1,K+1):
    for b in range(1,K+1):
        A = fractions.gcd(a,b)
        gcd[a-1][b-1] = A
        L[A-1] +=1

sum=0
for c in range(1,K+1):
    for i in range(1,K+1):
        B = gcd[c-1][i-1]
        sum +=  B * L[i-1]

print(sum)
### BUGGY CODE ###

import numpy as np

N,K = map(int,input().split())
p = input().split()

exps = []
ans = []

for ii in range(N):  
  p[ii] = int(p[ii])
  e = np.arange(1,p[ii]+1)
  exps.append(np.sum(e)/p[ii])

for ii in range(K-1,N):
  ans.append(np.sum(exps[ii-K+1:ii+1]))
    

print(np.max(ans))

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))

res = []

res.append((sum(range(1,p[0]+1)))/p[0])

for i in range(1,N):
  #res.append(res[i-1] + p[i]*(p[i]+1)/(2*p[i]))
  res.append(res[i-1] + 0.5*(p[i]+1))
  #res.append(res[i-1] + 1 + 0.5*(p[i]-1))

ans=res[K-1]

for i in range(1,N-K+1):
  ans = max(ans,res[i+K-1] - res[i-1])
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
s = input()
c = 0
while True:
    ns = ""
    p = ""
    f = [1] * len(s)
    for i in range(len(s)):
        if f[i] > 0:
            if i == len(s)-1:
                ns += s[i]
            elif s[i] != s[i + 1]:
                c += 2
                f[i + 1] = 0
            else:
                ns += s[i]
    if ns == s:
        break
    s = ns
print(c)


### FIXED CODE ###

#!/usr/bin/env python3
s = input()
n = len(s)
c = 0
p = ""
count = 0
for i in s:
    if i == p:
        count += 1
    else:
        c = count - c
        count = 1
    p = i
c = count - c
print(n - abs(c))
### BUGGY CODE ###

def solve(maze,H, W, S, G):
    next_ = [S]
    seen = [[False]*W for _ in range(H)]
    n = 0
    while True:
        curr_ = next_[:]
        next_ = []
        for h, w in curr_:
            if (h, w) == G:
                return n
            if seen[h][w]:
                continue

            seen[h][w] == True
            next_ += maze[h][w]
        n += 1
    
    return print('error')

# 入力
H, W = list(map(int, input().split()))
maze = [[[] for _ in range(W)] for _ in range(H)]
for h in range(H):
    row = input()
    for w in range(W):
        if row[w] == '#':
            maze[h][w] = False


# mazeに移動可能移動可能なマスを記録
for h in range(H):
    for w in range(W):
        if maze[h][w] == False:
            continue
        for nh, nw in [(h+1, w), (h, w+1), (h-1, w), (h, w-1)]:
            if 0 <= nh < H and 0<= nw < W:
                if maze[nh][nw] != False:
                    maze[h][w].append((nh, nw))
        # print(maze)
# print(maze)
ans = 0
for i in range(H*W-1):
    for j in range(i+1, H*W):
        S = (i//W, i%W)
        G = (j//W, j%W)
        if maze[S[0]][S[1]] and maze[G[0]][G[1]]:
            ans = max(ans, solve(maze, H, W, S, G))

print(ans)

### FIXED CODE ###

def solve(maze,H, W, S):
    next_set = set()
    next_set.add(S)
    seen = [[False]*W for _ in range(H)]
    n = 0
    while next_set:
        n += 1
        curr_ = list(next_set)
        next_set = set()
        for h, w in curr_:
            if seen[h][w]:
                continue
            seen[h][w] = True
            for nh, nw in maze[h][w]:
                if seen[nh][nw] == False:
                    next_set.add((nh, nw))
    return n-1

# 入力
H, W = list(map(int, input().split()))
maze = [[[] for _ in range(W)] for _ in range(H)]
for h in range(H):
    row = input()
    for w in range(W):
        if row[w] == '#':
            maze[h][w] = False


# mazeに移動可能移動可能なマスを記録
for h in range(H):
    for w in range(W):
        if maze[h][w] == False:
            continue
        for nh, nw in [(h+1, w), (h, w+1), (h-1, w), (h, w-1)]:
            if 0 <= nh < H and 0<= nw < W:
                if maze[nh][nw] != False:
                    maze[h][w].append((nh, nw))
        # print(maze)
# print(maze)
ans = 0
for i in range(H*W-1):
        h = i//W
        w = i%W
        if maze[h][w]:
            ans = max(ans, solve(maze, H, W, (h, w)))

print(ans)