Harryxun/stf_run huggingface dataset:
from functools import lru_cache

def main():
    n,m = map(int,input().split())
    A = []
    for _ in range(m):
        a = int(input())
        A.append(a)
    mod = 10**9+7
    @lru_cache(maxsize=1000000)
    def root(n):
        if n==0 or n==1:
            return 1
        else:
            if n-1 in A and n-2 in A:
                return 0
            elif n-1 in A and n-2 not in A:
                return root(n-2)%mod
            elif n-1 not in A and n-2 in A:
                return root(n-1)%mod
            else:
                return (root(n-1)+root(n-2))%mod
    print(root(n))

if __name__ == "__main__":
    main()

### FIXED CODE ###

from functools import lru_cache

def main():
    n,m = map(int,input().split())
    import numpy as np
    ans = np.ones(n+1,dtype=int)*-1
    ans[0] = 1
    mod = 10**9+7
    for _ in range(m):
        a = int(input())
        ans[a]=0
    if ans[1]!=0:
        ans[1]=1
    for i in range(2,n+1):
        if ans[i]!=0:
            ans[i] = (ans[i-1]+ans[i-2])%mod
    print(ans[-1])
        

if __name__ == "__main__":
    main()
n = int(input())
for i in range(n):
    a, b, c = list(map(int, input())).sort()
    if c ** 2 == (a ** 2 + b ** 2):
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n = int(input())
for i in range(n):
    a, b, c = sorted(list(map(int, input().split())))
    if c ** 2 == (a ** 2 + b ** 2):
        print("YES")
    else:
        print("NO")
_in = list(map(int, input().split()))
k = _in[0]
n = _in[1]
p = 0
_i = list(map(int, input().split()))
dis = 0
mdis = k - _i[n-1] + _i[0]
for i in range(0,n-2):
    dis = _i[i+1]- _i[i]
    if dis>mdis:
        mdis = dis
print(k-mdis)

### FIXED CODE ###

s = str(input())
if s[2]==s[3] and s[4]==s[5]:
    print("Yes")
else:
    print("No")
n,k = map(int,input().split())
ls = list(map(int,input().split()))
di = [1]
fi = [0]*(n+1)
a = 0
for i in range(k+1):
    if fi[ls[a]] == 0:
        fi[ls[a]] = i
        a = ls[a] - 1
    else:
        ind = fi[ls[a]]
        t = (k - ind) % (max(fi) - ind)
        t += ind
        print(fi.index(t))
        break
else:
    print(a)

### FIXED CODE ###

n,k = map(int,input().split())
ls = list(map(int,input().split()))
fi = [-1]*(n+1)
fi[1] = 0
a = 0
aa = 0
for i in range(k):
    if fi[ls[a]] == -1:
        fi[ls[a]] = i + 1
        aa = a
        a = ls[a] - 1
    else:
        ind = fi[ls[a]]
        t = (k - ind) % (max(fi) + 1 - ind)
        t += ind
        print(fi.index(t))
        break
else:
    print(ls[aa])
N, M, K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

a = [0]
b = [0]

for i in range(n):
    a.append(a[i] + A[i])

for i in range(m):
    b.append(b[i] + B[i])
    
ans, j = 0, m
for i in range(n + 1):
    if a[i] > k:
        break
    while a[i] + b[j] > k:
        j -= 1
    ans = max(ans, i + j)
print(ans)

### FIXED CODE ###

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

A = [0]
B = [0]

for i in range(n):
    A.append(A[i]+a[i])

for i in range(m):
    B.append(B[i]+b[i])
    
ans,j = 0,m
for i in range(n+1):
    if A[i] > k:
        break
    while B[j] > k - A[i]:
        j -= 1
    ans = max(ans,i+j)
print(ans)
n,k = map(int,input().split())
a = [0] + list(map(int,input().split()))
vcnt = [0]*(n+1)
vcnt[1] += 1
v = 1
sentou = 0
slist = []
vlist = [1]
hajime = 10**10
for i in range(1,k+1):
    v = a[v]
    vlist.append(v)
    vcnt[v] += 1
    if sentou > 0:
        syuuki += 1
    if vcnt[v] == 2:
        syuuki = 1
        sentou = a[v]
        slist.append(v)
    if vcnt[v] == 3:
        syuuki += 1
        hajime = i - syuuki*2
        break
else:
    print(v)
    exit()
#print(syuuki,hajime,sentou)
#print(slist)
k -= hajime
#print(slist)
slist = [0] + slist
if (k+1)%syuuki == 0:
    print(slist[-1])
else:
    print(slist[(k+1)%syuuki])

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,k = map(int,input().split())
alist = list(map(lambda x:int(x) - 1,input().split()))
count = [0]*n
count[0] += 1
now = 0
order = [0]
for i in range(k):
    now = alist[now]
    count[now] += 1
    if count[now] == 2:
        start = order.index(now)
        loop = len(order[start:])
        syoki = len(order[:start])
        break
    order.append(now)
else:
    print(now+1)
    exit()
k -= syoki
k %= loop
print(order[k+syoki] + 1)
a,b,c,d = map(int, input().split()

print(max( [a*c,a*d,b*c,b*d]  ))

### FIXED CODE ###

a,b,c,d = map(int, input().split())

print( max( [a*c,a*d,b*c,b*d] ))
n,k = map(int, input().split())
p = list(map(int, input().split())) 
c = list(map(int, input().split()))
r = -10**9
for i in range(n):
  ans=c[i]
  e =[ans]
  f = i
  a = 1
  while a<k:
    i = p[i]-1
    if i == f:
      break
    a+=1
    ans+=c[i]
    e.append(ans)
  if e[-1]>0 and a<k:
    w = k%len(e)
    y = k//len(e)*e[-1]+max(e[:w])
    g=y
  else:
    g=max(e)
  r = max(r,g)
  
print(r)

### FIXED CODE ###

n,k = map(int, input().split())
p = list(map(int, input().split())) 
c = list(map(int, input().split()))
r = -10**9
for i in range(n):
  ans=c[i]
  e =[ans]
  f = i
  a = 1
  while a<k:
    i = p[i]-1
    if i == f:
      break
    a+=1
    ans+=c[i]
    e.append(ans)
  if e[-1]>0 and a<k:
    w = k%len(e)
    if w!=0:
      y = k//len(e)*e[-1]+max(e[:w])
    else:
      y =( k//len(e)-1)*e[-1]+max(e)
    g=y
  else:
    g=max(e)
  r = max(r,g)
print(r)
k = input()
str = input()
l = len(str)
if l <= k:
  print(str)
  else:
    print(s[:k])

### FIXED CODE ###

k = int(input())
s = input()
if int(len(s)) <= k:
  	print(str(s))
else:
  	print(((str(s))[0:k]) + "...")
import math

N = int(input())
ans = 0
sqi = math.sqrt(N)
for i in range(1, int(sqi)+1):
    if (N-i)%i == 0:
        m = (N-i)//i
        if N//m == N%m:
        	ans += (N-i)//i
print(ans)

### FIXED CODE ###

import math

N = int(input())
ans = 0
ms = set()
sqi = math.sqrt(N)
for i in range(1, int(sqi)+1):
    if N % i == 0:
        ms.add(i-1)
        ms.add(N//i-1)
for m in ms:
    if m <= 0:
        continue
    if N//m == N%m:
        ans += m
print(ans)
a,b,c=list(map(str,input().split()))
if a[-1]==b[0] and b[-1]==c[0]:print('YES')
else print('NO')

### FIXED CODE ###

a,b,c=list(map(str,input().split()))
if a[-1]==b[0] and b[-1]==c[0]:print('YES')
else:print('NO')
import sys
input = sys.stdin.readline
N=int(input())
A=[]
C=[]
D=[]
for i in range(N):
    a,b=map(int,input().split())
    c,d=min(a,b),max(a,b)
    A.append((c,d))
    C.append(c)
    D.append(d)
#print(A,C,D,si,ti)
if N==1:
    print(0)
    sys.exit()
ans=(max(C)-min(C))*(max(D)-min(D))
cur=min(D)
ma=min(D)
T=10**19
for a,b in A:
    if a>ma:
        T=min(best,cur-ma)
        break
    T=min(T,cur-a)
    cur=max(cur,b)

print(min(ans,(max(D)-min(C))*T))

### FIXED CODE ###

import sys
input = sys.stdin.readline
N=int(input())
A=[]
C=[]
D=[]
for i in range(N):
    a,b=map(int,input().split())
    c,d=min(a,b),max(a,b)
    A.append((c,d))
    C.append(c)
    D.append(d)
A.sort()
#print(A,C,D,si,ti)
if N==1:
    print(0)
    sys.exit()
ans=(max(C)-min(C))*(max(D)-min(D))
cur=max(C)
ma=min(D)
T=10**19
for a,b in A:
    if a>ma:
        T=min(T,cur-ma)
        break
    T=min(T,cur-a)
    cur=max(cur,b)
print(min(ans,(max(D)-min(C))*T))
N = int(input())
K = int(input())
S = str(input())

s_up = list(S)
s_low = s_up[K-1].lower()
s_up [K-1] = s_low

for n in range(N):
    print(s_up[n], end='')

print()


### FIXED CODE ###

l = input().split()
N = int(l[0])
K = int(l[1])
S = str(input())

s_up = list(S)
s_up [K-1] = s_up[K-1].lower()

for n in range(N):
    print(s_up[n], end='')

print()
N, M = [int(a) for a in input().split()]
S = [[int(i) for i in input().split()] for _ in range(M)]
flag = 0
if([1,0] in S):
  flag = 1
  print(-1)
else:
  NUM = 0
  LIST = [-1 for _ in range(M)]
  for s,c in S:
    s -= 1
    if(LIST[s]==-1):
      NUM += c*(10**(N-s-1))
      LIST[s] = c
    else:
      if(LIST[s]!=c):
        flag = 1
        print(-1)
        break
      else:
        continue
  if(LIST[0] == -1):
    NUM += 10**(N-1)
  if(flag==0):
    print(NUM)

### FIXED CODE ###

N, M = [int(a) for a in input().split()]
S = [[int(i) for i in input().split()] for _ in range(M)]
flag = 0
NUM = 0
LIST = [-1 for _ in range(N)]
for s,c in S:
    s -= 1
    if(LIST[s]==-1):
        NUM += c*(10**(N-s-1))
        LIST[s] = c
    else:
        if(LIST[s]!=c):
            flag = 1
            print(-1)
            break
        else:
            continue
if(LIST[0] == -1):
    if(N>1):
        NUM += 10**(N-1)
    else:
        NUM = 0
elif(LIST[0] == 0):
    if(N>1):
        print(-1)
        flag = 1
    else:
        NUM = 0
if(flag==0):
    print(NUM)
import math
a,b,c,d = map(int,input().split())
if c <=0 or d <= 0:
    print("No")
ans = c * d // math.gcd(c,d)
i = a
j = a
while True:
    if i % c == 0:
        break
    i += 1
while True:
    if j % d == 0:
        break
    j += 1
k = min(i,j)
while True:
    if k % ans == 0:
        break
    k += 1
ii = (b-i)//c 
jj = (b-j)//d 
kk = (b-k)//ans 
print(b-a-ii-jj+kk)


### FIXED CODE ###

a,b,c,d = map(int,input().split())
cc = b//c -(a-1)//c
dd = b//d -(a-1)//d
#a,bの最大公約数
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

#a,bの最小公倍数
def lcm(a, b):
	return a * b // gcd (a, b)
cd = lcm(c, d)
cdcd = b//cd -(a-1)//cd
print(b-a+1-cc-dd+cdcd)
print("x" * len(int(input())))

### FIXED CODE ###

print("x" * len(input()))
N=int(input())
S=input()
L='ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'
ans=''
for i in range(len(S)):
  a=S[i]
  index=L.find(a)
  b=L[index+N]
  ans=ans+b
prin(ans)

### FIXED CODE ###

N=int(input())
S=input()
L='ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'
ans=''
for i in range(len(S)):
  a=S[i]
  index=L.find(a)
  b=L[index+N]
  ans=ans+b
print(ans)
a

### FIXED CODE ###

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

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

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

a = z
b = x
c = y

print("{} {} {}".format(a,b,c))
a=int(input())
b=int(input())

ab1=a+b
ab2=a-b
ab3=a*b
print (max(ab1,ab2,ab3))

### FIXED CODE ###

a,b=map(int,input().split())
 
ab1=a+b
ab2=a-b
ab3=a*b
print (max(ab1,ab2,ab3))
import heapq
N,K=map(int, input().split())
V=list(map(int, input().split()))

ans=-10**9
for l in range(K+1):
    for r in range(max(1,K+1-l)):
        for d in range(max(1,K+1-l-r)):
            h=V[:l]
            heapq.heapify(h)
            for i in range(r): heapq.heappush(h, V[-1-i])
            for i in range(min(d,len(h))): heapq.heappop(h)
            ans=max(ans,sum(h))
print(ans)

### FIXED CODE ###

import heapq
N,K=map(int, input().split())
V=list(map(int, input().split()))

ans=-10**9
for l in range(min(N,K)+1):
    for r in range(max(1,min(N,K)+1-l)):
        for d in range(max(1,K+1-l-r)):
            h=V[:l]
            heapq.heapify(h)
            for i in range(r): heapq.heappush(h, V[-1-i])
            for i in range(min(d,len(h))): heapq.heappop(h)
            ans=max(ans,sum(h))
print(ans)
root = list()


def dfs(A, num, N):
    if A[num] in root:
        return root.index(A[num])
    else:
        root.append(A[num])
        return dfs(A, A[num]-1, N)


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    start = dfs(A, 0, N)

    if K <= len(root):
        print(root[K-1])
    else:
        index = (K - start) % (len(root)-start)
        loop = root[start:]
        print(loop[index-1])


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

root = list()


def dfs(A, num, N, memo):
    if memo[A[num]-1] == 1:
        return root.index(A[num])
    else:
        root.append(A[num])
        memo[A[num]-1] = 1
        return dfs(A, A[num]-1, N, memo)


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    memo = [0] * N
    start = dfs(A, 0, N, memo)

    if K <= len(root):
        print(root[K-1])
    else:
        index = (K - start) % (len(root)-start)
        loop = root[start:]
        print(loop[index-1])


if __name__ == "__main__":
    main()
n, t = map(int, input().split())
ans = float('inf')
for i in range(n):
    c, t2 = map(int, input().split())
    if t2 <= t:
        ans = min(ans, c)
print('TLE' if ans = float('inf') else c)

### FIXED CODE ###

n, T = map(int,input().split())
cost = 10000
for i in range(n):
    c, t = map(int, input().split())
    if t <= T:
        cost = min(cost, c)
if cost == 10000:
    print('TLE')
else:
    print(cost)
a,b,c,d = map(int,input(),split())

if abs(a-b) <= d:
    print('Yes')

elif abs(a-b) <= d and abs(b-c) <= d:
    print('Yes')

else:
    print('No')



### FIXED CODE ###

a,b,c,d = map(int,input().split())

if abs(a-c) <= d:
    print('Yes')

elif abs(a-b) <= d and abs(b-c) <= d:
    print('Yes')

else:
    print('No')
N=int(input())
sisterN=[]
SISTERn=[]
SIStern=[]
for n in range(N):
    _=int(input())
    if _<30000:
        _s= _
        if sisterN.count(_s)==1:
            sisterN.remove(_s)
        else:
            sisterN.append(_s)
    elif 30001<_<70000:
        _m= _
        if SISterN.count(_m)==1:
            SISterN.remove(_m)
        else:
            SISterN.append(_m)
    else:
        _b= _
        if SISTERn.count(_b)==1:
            SISTERn.remove(_b)
        else:
            SISTERn.append(_b)
print(len(sisterN)+len(SISTERn)+len(SIStern))


### FIXED CODE ###

N=int(input())
S=set()

for n in range(N):
    _=int(input())
    if _ in S:
        S.remove(_)
    else:
        S.add(_)

print(len(S))
def dfs(u, cnt):
    cnt += point[u]
    counter[u] = cnt
    color[u] = GRAY
    for v in M[u]:
        if color[v] == WHITE:
            dfs(v, cnt)
    color[u] = BLACK

import sys
sys.setrecursionlimit(100000)

n, q = map(int, input().split())
M = [[] for _ in range(n)]
point = [0] * n
for i in range(n-1):
    a, b = map(int, input().split())
    M[a-1].append(b-1)
    M[b-1].append(a-1)
for i in range(q):
    p, x = map(int, input().split())
    point[p-1] += x
#print(M, point)
    
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * n

counter = [0] * n
dfs(0, 0)

print(*counter)


### FIXED CODE ###

def dfs(u, cnt):
    cnt += point[u]
    counter[u] = cnt
    color[u] = GRAY
    for v in M[u]:
        if color[v] == WHITE:
            dfs(v, cnt)
    color[u] = BLACK

import sys
sys.setrecursionlimit(1000000)

n, q = map(int, input().split())
M = [[] for _ in range(n)]
point = [0] * n
for i in range(n-1):
    a, b = map(int, input().split())
    M[a-1].append(b-1)
    M[b-1].append(a-1)
for i in range(q):
    p, x = map(int, input().split())
    point[p-1] += x
#print(M, point)
    
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * n

counter = [0] * n
dfs(0, 0)

print(*counter)
n = int(input())
s = input()
cnt1 = 0
cnt2 = 0
for i in range(n):
    if s[i] == '0':
        cnt1 += 1
    else:
        cnt2 += 1
print(min(cnt1, cnt2)*2)

### FIXED CODE ###

S = input()
z_cnt = 0
o_cnt = 0
for i in S:
    if i == '0':
        z_cnt += 1
    if i == '1':
        o_cnt += 1
print(len(S)-(max(z_cnt,o_cnt)-min(z_cnt,o_cnt)))
n=int(input())
t, a=map(int, input().split())
h=[int(i) for i input.split()]
temp=[abs(a-(t-k*0.006)) for k in h]
print(temp.index(min(temp))+1)

n = int(input())
t, a = map(int, input().split())
h = [int(i) for i in input().split()]
difference = [abs(a - (t - i * 0.006)) for i in h]
print(difference.index(min(difference)) + 1)

### FIXED CODE ###

n=int(input())
t, a=map(int, input().split())
h=list(int(i) for i in input().split())
temp=[abs(a-(t-k*0.006)) for k in h]
print(temp.index(min(temp))+1)
# ABC150C - Count Order
from itertools import permutations


def main():
    N, *PQ = map(int, open(0).read().split())
    P, Q = PQ[:N], PQ[N:]
    perms = list(permutations(range(1, N + 1)))
    ans = abs(perms.index(P) - perms.index(Q))
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

# ABC150C - Count Order
from itertools import permutations


def main():
    N, *PQ = map(int, open(0).read().split())
    P, Q = PQ[:N], PQ[N:]
    a, b = 0, 0
    for i, perm in enumerate(permutations(range(1, N + 1), N), 1):
        perm = list(perm)
        if perm == P:
            a = i
        if perm == Q:
            b = i
    ans = abs(a - b)
    print(ans)


if __name__ == "__main__":
    main()
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


H, W, M = MI()
h = [0] * (H * W)
w = [0] * (H * W)
item_list = [[0, 0] for _ in range(M)]

for i in range(M):
    item_h, item_w = MI()
    h[item_h] += 1
    w[item_w] += 1
    item_list[i][0] = item_h
    item_list[i][1] = item_w

ans = max(h) + max(w)
d =[h.index(max(h)), w.index(max(w))]
if d in item_list:
    ans -= 1


print(ans)

### FIXED CODE ###

import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


H, W, M = MI()
h = [0] * H
w = [0] * W
item_list = [[0, 0] for _ in range(M)]

for i in range(M):
    item_h, item_w = MI()
    item_h -= 1
    item_w -= 1
    h[item_h] += 1
    w[item_w] += 1
    item_list[i][0] = item_h
    item_list[i][1] = item_w

h_max = max(h)
w_max = max(w)
h_cnt = h.count(h_max)
w_cnt = w.count(w_max)
ans = h_max + w_max

cnt = 0
for item in item_list:
    if h[item[0]] == h_max and w[item[1]] == w_max:
        cnt += 1

x = h_cnt * w_cnt
if cnt == x:
    ans -= 1

print(ans)
# coding: utf-8
import sys

     
def solve(a,begin,end,queue):
      if begin>=end:
        return
      maxx = sorted(list(map(abs,a[begin:end+1])),reverse=True)[0]
      if maxx in a:
        m = a.index(maxx)
      else:
        m = a.index(-1*maxx)
        maxx = -1*maxx
      if maxx==0:
        return []
      if maxx>0:
        solve(a,begin,m-1,queue)
        for i in range(max(0,m-1),end):
          if a[i+1]>=a[i]:
            continue
          else:
            a[i+1]+=a[i]
            queue.append((i,i+1))
            if a[i+1]<a[i]:
              a[i+1]+=a[i]
              queue.append((i,i+1))
        return queue
      if maxx<0:
        solve(a,m+1,end,queue)
        for i in reversed(range(begin,min(len(a)-1,m+1))):
          if a[i]<=a[i+1]:
            continue
          else:
            a[i]+= a[i+1]
            queue.append((i+1,i))
            if a[i]>a[i+1]:
              a[i]+=a[i+1]
              queue.append((i+1,i))
        return queue
     
if __name__ == '__main__':
      n = int(input())
      a = list(map(int,input().split()))
      queue = solve(a,0,len(a)-1,[])
      print(len(queue))
      for i in range(len(queue)):
        print(queue[i][0]+1,queue[i][1]+1)


### FIXED CODE ###

# coding: utf-8
import sys


def solve(a, begin, end, queue, cnt):
    #print(begin, end)
    if begin >= end:
        return
    maxx = sorted(list(map(abs, a[begin:end + 1])), reverse=True)[0]
    # print(maxx)
    if maxx in a[begin:end + 1]:
        m = a[begin:end + 1].index(maxx) + begin
    else:
        m = a[begin:end + 1].index(-1 * maxx) + begin
        maxx = -1 * maxx
    #print(m, maxx)
    if maxx == 0:
        return []
    if maxx > 0:
        solve(a, begin, m - 1, queue, cnt + 1)
        for i in range(max(0, m - 1), end):
            if a[i + 1] >= a[i]:
                continue
            else:
                a[i + 1] += a[i]
                queue.append((i, i + 1))
                if a[i + 1] < a[i]:
                    a[i + 1] += a[i]
                    queue.append((i, i + 1))
        return queue
    if maxx < 0:
        solve(a, m + 1, end, queue, cnt + 1)
        for i in reversed(range(begin, min(len(a) - 1, m + 1))):
            if a[i] <= a[i + 1]:
                continue
            else:
                a[i] += a[i + 1]
                queue.append((i + 1, i))
                if a[i] > a[i + 1]:
                    a[i] += a[i + 1]
                    queue.append((i + 1, i))
        return queue


if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    queue = solve(a, 0, len(a) - 1, [], 0)
    print(len(queue))
    for i in range(len(queue)):
        print(queue[i][0] + 1, queue[i][1] + 1)
import sys
from collections import deque

dx_list = [1, 0, -1, 0]
dy_list = [0, -1, 0, 1]
def bfs(h_len, w_len):
    cnt = 0
    while len(bfs_q)>0:
        u_list = bfs_q.popleft()
        h, w = u_list[0], u_list[1]
        tmp = m[h][w]
        for dx, dy in zip(dx_list, dy_list):
            x = w + dx
            y = h + dy
            if 0 <= x < w_len and 0 <= y < h_len and m[y][x] == -1:
                m[y][x] = tmp + 1
                cnt = max(cnt, tmp + 1)
                bfs_q.append([y, x])
    return cnt


if __name__ == "__main__":
    input = sys.stdin.readline
    h_len, w_len = map(int, input().split())
    m = [[-1]*h_len for _ in range(w_len)]
    a_list = []
    for _ in range(h_len):
        s = input()[:-1]
        a_list.append(s)
    bfs_q = deque([])
    for h, w_list in enumerate(a_list):
        for w, a in enumerate(w_list):
    	    if a == '#':
    		    m[h][w] = 0
    		    bfs_q.append([h, w])
    ans = bfs(h_len, w_len)
    print(ans)
	

### FIXED CODE ###

def bfs(q_list):
    cnt = -1
    while q_list:
        cnt += 1
        new_q_list = []
        for h, w in q_list:
            if not m_list[h][w+1]:
                m_list[h][w+1] = True
                new_q_list.append((h, w+1))
            if not m_list[h+1][w]:
                m_list[h+1][w] = True
                new_q_list.append((h+1, w))
            if not m_list[h][w-1]:
                m_list[h][w-1] = True
                new_q_list.append((h, w-1))
            if not m_list[h-1][w]:
                m_list[h-1][w] = True
                new_q_list.append((h-1, w))
        q_list = new_q_list
    print(cnt)


if __name__ == "__main__":
    h_len, w_len = map(int, input().split())
    m_list = [[True for _ in range(w_len+2)]]
    for _ in range(h_len):
        m_list.append([True] + [s=='#' for s in input()] + [True])
    m_list.append([True for _ in range(w_len+2)])
    q_list = []
    for h in range(1, h_len+1):
        for w in range(1, w_len+1):
            if m_list[h][w]:
                q_list.append((h, w))
    bfs(q_list)
A=input()

B=input()


ad=int(A)+int(B)
mi=int(A)-int(B)
de=int(A)*int(B)

math=[ad,mi,de]
m_max=max(math)

print(m_max)


### FIXED CODE ###

A,B=input().split()

ad=int(A)+int(B)
mi=int(A)-int(B)
de=int(A)*int(B)

math=[ad,mi,de]

m_max=max(math)

print(m_max)
import sys
from itertools import accumulate

def main():
    
    # sys.stdin = open('input154d.txt')

    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    
    s = [0] + p
    s = list(accumulate(s))
    print(p)
    print(s)

    maxp = 0
    index = 0
    for i in range(k, n):
      nowp = s[i] - s[i - k]
      if maxp < nowp:
        maxp = nowp
        index = i

    sump = 0
    for j in range(i-k, i):
      sump += p[j] * (p[j] + 1) / 2 / p[j]

    print(sump)
        
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from itertools import accumulate

def main():
    
    # sys.stdin = open('input154d.txt')

    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    
    s = [0] + p
    s = list(accumulate(s))

    # print(p)
    # print(s)
    maxp = 0
    idx = 0
    for i in range(n - k + 1):
      nowp = s[i + k] - s[i]
      # print(i)
      # print(nowp)
      if maxp < nowp:
        maxp = nowp
        idx = i

    # print(idx)

    sump = 0
    for j in range(idx, idx+k):
      sump += p[j] * (p[j] + 1) / 2 / p[j]

    print(sump)
        
if __name__ == '__main__':
    main()